문제 링크
문제
티어: 플레 5
알고리즘: dp
상덕이와 희원이는 소문난 환상의 듀엣으로, 노래방에 가서 노래를 자주 부르곤 한다. 어느 날 상덕이는 백준이에게 선물 받은 악보를 가져왔다. 악보에는 그 노래를 표현하는데 필요한 음의 높이가 순서대로 N개 적혀져 있었다. 둘은 악보에 적혀 있는 모든 음들을 노래해야 하며, 각 음은 둘 중 한 사람에 의해서만 불러져야 한다. 예를 들어 악보에 {3, 6, 2, 5, 4}가 적혀져 있을 때, 상덕이가 {3, 2, 4}을 노래하면 희원이는 {6, 5}를 노래할 것이고, 상덕이가 {6, 2, 5}을 노래하면 희원이는 {3, 4}를 노래할 것이다.
노래를 부르다 음의 높이를 변경하는 것은 힘든 일이다. 예를 들어 {4, 6}을 부르는 것은 {4, 4}를 부르는 것에 비해서 음의 변경이 발생하기 때문에 더 힘들다고 볼 수 있다. 희원이는 {a1, a2, ..., ak}라는 음들의 집합을 노래할 때 힘든 정도를 |a1 - a2| + |a2 - a3| + ... + |ak-1 - ak|로 정의했다. 노래를 부르는 사람은 상덕이와 희원이 둘 뿐이므로, 음들을 집합은 두 개가 있을 것이다. 따라서 두 사람이 해당 악보를 노래를 할 때 힘든 정도는 두 집합의 힘든 정도의 합으로 표현될 수 있다.
상덕이와 희원이는 해당 악보를 노래할 때 힘든 정도를 최소화하고 싶다. 예를 들어 악보가 {1, 3, 8, 12, 13}으로 주어진다하자. 앞의 2개를 상덕이가 부르고 뒤의 3개를 희원이가 부르게되면 상덕이의 힘든 정도는 |1 - 3| = 2, 희원이의 힘든 정도는 |8 - 12| + |12 - 13| = 5가 되며 합인 7이 총 힘든 정도가 되고, 이 값은 나올 수 있는 힘든 정도 중에 가장 최솟값이다. 상덕이와 희원이를 위해서 해당 악보를 노래할 때 힘들 수 있는 정도의 최솟값을 알려주는 프로그램을 작성해보자.
입력
첫 번째 줄에는 음의 개수 N (1 ≤ N ≤ 2,000)이 주어진다.
두 번째 줄에는 N개의 음의 높이가 공백(빈 칸)으로 구분되어 주어진다. 각 음의 높이의 범위는 1 이상 1,000,000 이하의 자연수이다.
출력
상덕이과 희원이가 해당 악보를 노래할 때 힘들 수 있는 정도의 최솟값을 출력한다.
풀이
상덕이와 희원이를 위해서 해당 악보를 노래할 때 힘들 수 있는 정도의 최솟값을 출력해야 한다.
노래할 때는 해당 악보의 모든 음을 반드시 불러야 한다.
그러면 다음과 같은 악보가 있을 때
1 3 8 12 13
에서 1 3 8 12까지 불렀을 경우 상덕이와 희원이는 이 4개의 음을 나눠서 불렀을 것인데, 이 상황에서의 최솟값이 다음 13을 불렀을 때 최솟값을 보장하지 않는다. (마지막에 어떠한 음을 불렀는 지에 따라서도 값이 달라지기 때문)
그렇기 때문에 상태는 상덕, 희원이가 마자막에 어떠한 음을 불렀는 지를 나타내야 된다.
단순히 이렇게 정의했을 때 시간 복잡도가 N^3이기 때문에 불가능한데, 잘 생각해 보면, 상덕이나 희원이 둘 중 하나는 마지막 음이 현재 음에서 바로 전 음이 된다.
예를 들어 1 3 8 12까지 불렀을 때 누군가는 반드시 마지막 음이 12가 된다.
그래서 13에서는 12에서 -> 13,
1, 3, 8에서 -> 13을 계산하면 되기 때문에 N^2으로 줄일 수 있다.
이를 토대로 dp를 정의하면 dp[마지막 음1][마지막 음2]이며,
마지막 음1은 마지막 음2보다 항상 큰 값을 가진다는 제한을 두면, 불필요한 횟수도 줄일 수 있다. 그래서 dp[4][1]은 마지막 음1이 4이고, 마지막 음2가 1일 때 최솟값을 의미한다.
다시 예제 입력 1로 돌아와서
1 3 8 12 13
에서 dp[5][0], dp[5][1], dp[5][2], dp[5][3], dp[5][4]
를 구하는 과정을 생각해 보자,
dp[5][1]은 dp[4][1]에서 arr[4] -> arr[5]로 할 수 있는 경우가 있다.
그래서 dp[5][1] = Math.min(dp[5][1], dp[4][1] + Math.abs(arr[4] - arr[5]));
dp[5][4]같은 경우는 dp[4][0], dp[4][1], dp[4][2], dp[4][3]에서 arr[5]를 부를 수 있는데, 이는 (0, 1, 2, 3 -> 5)를 부르는 경우다.
그래서 다음과 같은 식이 된다.
dp[5][4] = Math.min(dp[5][4], dp[4][0] + 0); //0에서는 음이 없는 상태이기 때문
dp[5][4] = Math.min(dp[5][4], dp[4][1] + Math.abs(arr[1] - arr[5]));
dp[5][4] = Math.min(dp[5][4], dp[4][2] + Math.abs(arr[2] - arr[5]));
dp[5][4] = Math.min(dp[5][4], dp[4][3] + Math.abs(arr[3] - arr[5]));
이 풀이의 시간 복잡도는 O(N^2)이다.
소스 코드
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());
int[] arr = new int[N + 1];
StringTokenizer st = new StringTokenizer(br.readLine());
for(int i=1; i<=N; i++) {
arr[i] = Integer.parseInt(st.nextToken());
}
int[][] dp = new int[N + 1][N + 1];
init(dp);
dp[1][0] = 0;
for(int i=2; i<=N; i++) {
//이번에 불려야 될 음 => i
for(int j=0; j<=i-2; j++) {
//dp[i - 1][0 ~ ...]
//(i - 1)에서 i를 부르는 경우
dp[i][j] = Math.min(dp[i][j], dp[i - 1][j] + Math.abs(arr[i - 1] - arr[i]));
//j에서 i를 부르는 경우
dp[i][i - 1] = Math.min(dp[i][i - 1], dp[i - 1][j] + (j == 0 ? 0 : Math.abs(arr[j] - arr[i])));
}
}
int answer = Integer.MAX_VALUE;
for(int i=0; i<=N - 1; i++) {
answer = Math.min(answer, dp[N][i]);
}
System.out.println(answer);
}
static void init(int[][] dp) {
for(int i=0; i<dp.length; i++) {
for(int j=0; j<dp[i].length; j++) {
dp[i][j] = Integer.MAX_VALUE;
}
}
}
}