문제 이해
파일이 여러 개 존재하고, 이런 파일들을 한 개의 파일로 묶으려고 한다.
이 때 파일은 한 번에 2개씩만 묶을 수 있고, 2개의 파일을 묶은 이후 해당 묶음은 한 개의 파일으로 간주한다.
아래와 같은 조건으로 파일을 합칠 때, 필요한 총 비용이 가장 적게 드는 최소 비용을 구하는 문제이다.
-
A와 B를 묶을 때는 (A의 수치 + B의 수치)만큼 비용이 필요하다.
-
연속으로 존재하는 파일들밖에 묶을 수 없다(A B C의 경우, A와 C를 바로 묶을 수는 없음)
- 총 비용 : 묶을 때 필요한 중간 비용을 모두 더한 값
문제 풀이
현재 N ~ M의 연속된 파일을 묶는다고 가정하자.
항상 연속으로 존재하는 파일들만 묶을 수 있으므로, 이 파일을 만드는 방법은 아래와 같다.
-
N 파일 + { (N+1) ~ M 묶음 }
-
{ N ~ (N+1) 묶음 } + { (N+2) ~ M 묶음 }
...
- {N ~ (M-1) 묶음} + M 파일
우리가 최종적으로 구하고 싶은 값은 1 ~ N 파일을 모두 합친 결과이다.
따라서, DP 값을 저장할 배열을 N * N으로 지정했다. 또한 DP[i][j]를 i ~ j의 연속된 파일을 묶을 때 드는 최소 비용이라고 생각했다.
DP[N][M]을 구하기 위해서는, 먼저 DP[N+1][M] ~ DP[M][M], DP[N][N] ~ DP[N][M-1]이 계산 되어 있어야 할 것이다.
즉 배열 값을 아래에서 부터 채우고, 같은 행이라면 왼쪽에서 부터 채우는 점화식을 활용해야 한다.
이 때, 중요한 사항이 있다.
우리는 "묶을 때 필요한 중간 비용을 모두 더한 값"을 구하고 싶은 것이다.
따라서 DP 배열은 이런 중간 비용에 대한 처리가 필수적이다.
방법이 어떤 방법이든, N~M까지의 파일을 합치는데 필요한 총 비용은 cost[N] + cost[N+1] + cost[N+2] + ... cost[M]이라는 것을 알 수 있다.
즉, DP[N][M] = DP[N][K] + DP[K][M]만을 수행한다면, "N ~ M을 만드는 당시 상황"만을 파악하는게 될 것이다.
조금 더 세부적으로 설명하겠다(이 부분 때문에 골머리를 많이 썩였다)
10 20 30 40파일이 존재한다고 가정하자.
만약 10 + 20, 30 + 40으로 묶은 뒤 마지막 2개를 묶었다고 생각하자. 이 경우, DP[N][M] = DP[N][K] + DP[K][M]만을 활용한다면 DP[1][4] = 100이 될 것이다.
물론, (10,20), (30,40)으로 2개의 파일이 묶어진 이후의 중간 비용은 100이 맞을 것이다.
하지만 이 경우, (10,20)을 만들기 위한 30과 (30,40)을 만들기 위한 70은 어디에서도 계산할 수가 없다.
DP[i][i+2]를 생각해보자.
-
DP[i][i] + DP[i+1][i+2] = (파일 i의 크기) + (i+1 ~ i+2 묶음 파일 크기)
-
DP[i][i+1] + DP[i+2][i+2] = (i ~ i+1 묶음 파일 크기) + (파일 i+2의 크기)
이 경우, "더해지는 당시 상황"만을 구하는 공식이다. 그렇다면, i+1 ~ i+2 묶음을 위한 중간 과정은 어디에서 처리해야 하는가?
문제를 파악하다보면, DP[N][M], 즉 N~M 파일을 묶을 때 드는 비용은 그 전 과정과는 관계 없이 cost[N] + cost[N+1] + ... + cost[M]이라는 것을 알 수 있다. 즉, 묶음에 들어 있는 모든 파일 크기의 합이 파일을 묶을 때 드는 당시의 비용이다.
그렇다면 DP를 "묶을 때 드는 비용"이 아닌, "묶을 때 사용한 중간 비용"을 저장하는 배열로 사용하면 되지 않을까?
어차피 묶을 때 드는 비용은 이미 정해져 있기 때문이다.
(N~M묶음) = (N ~ T 묶음) + (T+1 ~ M묶음) 이라고 생각하자.
DP[N][T] = N ~ T를 묶을 때 필요한 비용(N ~ T까지의 합) + (N ~ T 묶음을 만들기 위한 이전 비용)
DP[T+1][M] = T+1 ~ M을 묶을 때 필요한 비용(T+1 ~ M까지의 합) + (T+1 ~ M 묶음을 만들기 위한 이전 비용)
⇒ DP[N][M] = DP[N][T] + DP[T+1][M] + (N ~ M까지의 합)
= (N ~ T를 만들 때 까지 걸린 중간 비용의 합) + (T+1 ~ M을 만들 때 까지 걸린 중간 비용의 합) + (N ~ M을 만들기 위한 비용)
= N ~ M을 만들기 위한 중간 비용의 총 합
코드
import java.io.*;
import java.util.*;
public class Main {
static StringBuilder sb = new StringBuilder();
static int N;
static int[][] dp_arr;
// dp_arr[i][j] : i~j번째 파일을 묶었을 때 필요한 중간 비용의 합 중 최솟값
static int[][] sum;
// sum[i][j] : i ~ j번째 파일의 크기 합
static void pre() {
for(int i=N;i>0;i--) {
for(int j =i+1;j<=N;j++) {
sum[i][j] = sum[i][j-1]+sum[j][j];
}
}
}
static void dp() {
for(int i =N;i>0;i--) {
for(int j = i+1;j<N+1;j++) {
dp_arr[i][j] = Integer.MAX_VALUE;
for(int mid = i;mid<j;mid++) {
dp_arr[i][j] = Math.min(dp_arr[i][mid]
+dp_arr[mid+1][j]+sum[i][j], dp_arr[i][j]);
/*
i : N부터 시작하여 감소하는 형식으로 설정.
배열 아래에서부터 값을 정해야 함
j : i+1부터 시작하여 증가하는 형식으로 설정.
같은 행일 경우 왼쪽에서부터 값 정함
즉, i,j를 통해 배열의 아래에서 위쪽으로,
같은 행에서는 왼쪽에서 오른쪽으로 값 초기화
문제 풀이에서 나온 방법대로
dp_arr[i][mid] + dp_arr[mid+1][j]+ sum[i][j] 활용
최솟값을 구하는 것이므로 최솟값을 저장해 놓아야 함
*/
}
}
}
}
public static void main(String[] args) throws IOException {
FastReader sc = new FastReader();
int T = sc.nextInt();
for(int t = 0;t<T;t++) {
N = sc.nextInt();
dp_arr = new int[N+1][N+1];
sum = new int[N+1][N+1];
for(int i =1;i<N+1;i++) {
sum[i][i] = sc.nextInt();
}
pre(); // sum 배열 초기화
dp();
sb.append(dp_arr[1][N]).append("\n");
}
System.out.println(sb);
}
static class FastReader // 빠른 입력을 위한 클래스
}
결과
