시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 128 MB | 592 | 203 | 152 | 34.624% |
수열 a1, ..., an이 주어졌을 때, reduce(i)는 ai와 ai+1를 max(ai, ai+1)로 바꾸는 연산이다. 이 연산을 사용하면 수열의 길이는 1만큼 작아지게 된다.
reduce연산의 비용은 max(ai, ai+1)과 같다. 연산을 n-1번 사용하면, 수열의 길이는 1이 된다.
reduce연산을 n-1번 사용해서, 수열의 길이를 1로 만들 때, 연산의 비용의 합의 최솟값을 구하는 프로그램을 작성하시오.
첫째 줄에 수열의 길이 n(1 ≤ n ≤ 1,000,000)이 주어진다. 다음 n개의 줄에는 수열의 원소 ai가 순서대로 주어진다. (0 ≤ ai ≤ 1,000,000,000)
첫째 줄에 수열의 길이를 1로 만드는데 드는 비용의 합의 최솟값을 출력한다.
3 1 2 3
5