[BOJ] #3366 수열 줄이기

시간 제한	메모리 제한	정답 비율
1초	128MB	37.179%

3366번: 수열 줄이기

 

문제

수열 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)

 

해결

key point, stack 활용!

1. reduce 연산의 비용이 max(ai, ai+1) 이므로 연산의 최솟값은 가장 작은 ai부터 차례대로 진행해야한다.
2. 입력받은 수열을 arr[]에 저장하고 스택을 stack[] 일때
3. stack의 가장 위에있는 값보다 arr[i] 값이 더 작으면 stack에 쌓는 방식으로 stack[top-1] 위치에 있는 값이 수열의 i번째 까지의 최솟값임을 보장한다.
4. 그 외의 경우에는 stack[top-1]에 위치한 값과 reduce연산을 하게 되는데 왼쪽에 위치한 원소와 연산 할것인지, 오른쪽에 위치한 원소와 연산할것인지 정해야한다.
   • 왼쪽에 위치한 원소와 연산을 할 경우에는 stack[top-2]가 arr[i]보다 작은 경우이다. 그러면 stack[top-1]에 있던 값보다 stack[top-2]에 있는 값이 당연히 크므로 연산의 비용은 stack[top-2]가 된다. 그리고 max값만 남게 되므로 stack[top-1]을 지운다는 의미로 top--만 해주면 된다.
   • 오른쪽에 위치한 원소와 연산을 할 경우에는 스택에 쌓아놓았던 어느 값보다 arr[i]값이 더 작을 때이다. 이 때는 연산의 비용이 arr[i]가 되고, 연산의 결과는 max값만 남게 되므로 stack[top-1] 위치에 arr[i]가 저장되게 된다.
5. 반복문이 모두 끝나고 마지막에 스택에 2개 이상의 값이 남아있다면 거꾸로 반복문을 돌면서, 두 개의 원소 중 더 스택 아래에 있는 값을 연산의 비용으로 더한다.
6. 마지막으로 모든 연산의 비용을 더했던 ans변수를 long long 형으로 출력한다.
   • 수열의 원소는 최대 10억이고, 수열의 길이는 100만 이므로 계속해서 더해가면 int 범위를 넘기때문에 long형으로 선언해야한다.

 

코드

메모리	시간
9796 KB	212 ms