문제 링크
문제
티어: 골드 1
알고리즘: 그리디
수열 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로 만드는데 드는 비용의 합의 최솟값을 출력한다.
풀이
수열의 길이를 1로 만드는데 드는 비용의 합의 최솟값을 출력해야 한다.
1 2 3 수열이 있을 때
만약 (2, 3)을 먼저 연산을 한다면 max 값인 3이 된다. 그러면 min이였던 2가 수열에서 없어지게 되는데, 이 2를 최대한 활용하는 것이 당연히 최적해가 될 것이다.
2를 최대한 활용한다는 의미는 2가 max가 되는 쌍이 있다면 최대한 활용해야 함을 뜻한다.
(2, 3)을 먼저하면, 그러한 가능성 자체를 없애버리기 때문에 (2, 3)을 먼저 연산하는 것은 최적해가 될 수 없다.
그러면 이를 일반화해보면, 작은 값들을 최대한 활용하는 것이 최적해가 될 수 있다.라는 결론에 도달하고, 작은 값들을 최대한 활용한다는 것은 초기에 인접한 요소와의 연산 결과 값 중 가장 작은 값을 우선적으로 선택해 나가는 것이며, 최적해를 보장한다.
다른 방식으로 생각해 봐도, 초기에 연산 결과를 나열해 봤을 때 그 연산 결과를 줄이는 방법은 존재하지 않지만, 연산 순서에의해서 값이 커지는 경우는 존재한다. 이는 다시 말해서 초기 연산 결과를 최대한 유지해야함을 의미한다.
1 2 3을 다시 보면, 인접한 연산 결과를 나열했을 때 2 3이 된다. (1 , 2) -> 2, (2, 3) -> 3으로
여기서 연산 결과가 가장 작은 값은 2고, 수열은 2 3이 된다.
(2, 3)은 3이기 때문에 최적해는 5가 되는 것이다.
그러면 매번 수열이 바뀌기 때문에 연산 결과를 업데이트해야 될 것 같은 느낌이 든다.
그런데 생각해 보면, 우리는 가장 작은 연산 결과 값을 우선적으로 연산하기 때문에 초기에 구해놓은 연산 결과는 변하지 않는다.
예를 들어 1 2 3에서 (1, 2)의 연산 결과가 (2, 3)보다 작은 2이기 때문에 먼저 수행하는데 그 결과가 어차피 가장 작은 연산 결과 값이기 때문에 인접한 요소간에 연산 결과값도 그대로 유지된다.
즉, 초기에 연산 결과가 최대한 유지되는 것이 최적해지만 정확히 말하면 초기에 연산 결과를 그대로 유지하는 것이 최적해이며 그 방법이 "가장 작은 연산 결과를 우선적으로 연산하는 것"이라는 결론에 도달한다.
그래서 초기 연산 결과 값을 그대로 더해주면 그 값이 최적해가 되는 것이다.
(1 2 3인 경우는 2 3이며, 2 + 3 = 5로 최적해인 것처럼)
이 풀이의 시간 복잡도는 O(N)이다.
소스 코드
import java.io.*;
import java.util.*;
public class Main {
static int N;
public static void main(String args[]) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
long answer = 0;
int before = Integer.parseInt(br.readLine());
for(int i=1; i<N; i++) {
int num = Integer.parseInt(br.readLine());
answer += Math.max(before, num);
before = num;
}
System.out.println(answer);
}
}