문제
K개의 파일을 하나로 합친다. 두 파일을 합칠 때 비용은 두 파일 크기의 합이다. 모든 파일을 하나로 합치는 최소 비용을 구한다. K가 최대 5,000이고 테스트 케이스가 여러 개다.
입력
- 첫째 줄: 테스트 케이스 수 T
- 각 테스트 케이스: K (파일 수), K개의 파일 크기
출력
각 테스트 케이스마다 최소 합치기 비용을 출력한다.
예제
| 입력 | 출력 |
|---|---|
1 4 40 30 30 50 | 300 |
풀이
구간 DP로 dp[i][j] = i번째부터 j번째 파일까지 합치는 최소 비용을 정의한다. dp[i][j] = min(dp[i][k] + dp[k][j]) + sum[j] - sum[i]가 기본 점화식이다. K가 5,000이라 O(K^3)이면 시간 초과이므로 크누스 최적화로 O(K^2)로 줄인다.
- 부분 합 배열
sum을 전처리하여 구간 합을 O(1)에 계산한다. num[i][j]= dp[i][j]를 최소로 만드는 분할 지점 k를 저장한다.- 크누스 최적화 조건:
num[i][j-1] <= k <= num[i+1][j]로 탐색 범위를 제한한다. - 구간 크기를 2부터 K까지 늘려가며 최소 비용을 계산한다.
- 최종
dp[0][K]를 출력한다.
핵심 아이디어: 구간 DP의 분할 지점을 전체 탐색하면 O(K^3)이지만, 크누스 최적화를 적용하면 최적 분할 지점의 단조성(opt[i][j-1] ≤ opt[i][j] ≤ opt[i+1][j])을 이용해 총 O(K^2)로 줄인다. 인덱스를 dp[i][k] + dp[k][j] 형태로 변환(기존 dp[i][k] + dp[k+1][j]와 달리)하여 경계 처리를 단순화한다.
코드
package com.ssafy.an.day099;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Day97BOJ13974파일합치기2DP크누스최적화 { // 13974 파일 합치기 2 DP 크누스최적화
static int T, K;
static int[] arr, sum;
static int[][] dp, num;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
StringTokenizer st = null;
T = Integer.parseInt(br.readLine());
while (T-- > 0) {
K = Integer.parseInt(br.readLine());
arr = new int[K + 1];
sum = new int[K + 1];
num = new int[K + 1][K + 1];
dp = new int[K + 1][K + 1];
st = new StringTokenizer(br.readLine());
for (int i = 1; i < K + 1; i++) {
arr[i] = Integer.parseInt(st.nextToken());
sum[i] = sum[i - 1] + arr[i]; // 부분합 배열
num[i - 1][i] = i; // 크누스 알고리즘
}
for (int n = 2; n < K + 1; n++) { // n차이값인데, 이미 i-1과 i값은 초기화되어있다.
for (int i = 0; i + n < K + 1; i++) {
int j = i + n;
dp[i][j] = Integer.MAX_VALUE;
for (int k = num[i][j - 1]; k < num[i + 1][j] + 1; k++) {
int v = dp[i][k] + dp[k][j] + sum[j] - sum[i];
if (dp[i][j] > v) {
dp[i][j] = v; // 최소값으로 갱신
num[i][j] = k; // 최소값 k를 찾아 보존
}
}
// sb.append(print(num) + "\n"); // 최소값 num배열 출력
}
}
sb.append(dp[0][K] + "\n"); // 1~K가 아닌, 0~K
}
System.out.println(sb);
br.close();
}
private static String print(int[][] a) {
StringBuilder t = new StringBuilder();
for (int i = 0; i < a.length; i++) {
for (int j = 0; j < a[i].length; j++)
t.append(String.format("%3d", a[i][j]));
t.append("\n");
}
return t.toString();
}
}
// 기존 index i <= k < j
// dp[i][j] = min(i <= k < j){dp[i][k] + dp[k+1][j]} + psum[i][j]
// 변경 index i < k < j
// dp[i][j] = min(i < k < j){dp[i][k] + dp[k][j]} + psum[i][j]
// 기존에는 최소비용의 k값을 i 자기 자신까지 비교하여 최소비용을 유지 하지만,
// 크누스 알고리즘에서는 k값을 i와 j복잡도
- 시간: O(K^2) — 크누스 최적화 적용으로 O(K^3)에서 개선
- 공간: O(K^2) — dp 및 num 2차원 배열