[Algorithm] cpp 백준 13974번: 파일 합치기 2

연속한 파일만 합칠 수 있을 때 최소 비용을 구하는 구간 DP 문제입니다. dp[i][j]=min(dp[i][k]+dp[k+1][j])+sum(i..j)에 크누스 최적화를 적용해 O(N^2)로 해결합니다. 누적합으로 구간합을 O(1)로 계산하며 64비트 정수, 메모리 사용에 유의합니다.

문제

링크: https://www.acmicpc.net/problem/13974
요약: 크기가 주어진 K개의 장(파일)을 연속성이 유지되도록 두 개씩 합쳐 한 개가 될 때까지 진행한다. 두 파일을 합칠 때의 비용은 두 파일 크기의 합이며, 전체 최소 비용을 구한다.

제한/스펙

테스트케이스 T
3 ≤ K ≤ 5000, 각 파일 크기 1..10000
시간 6초, 메모리 512MB

입출력 형식/예제

예제 입력 1

1
2
3
4
5
2
4
40 30 30 50
15
1 21 3 4 5 35 5 4 3 5 98 21 14 17 32

예제 출력 1

접근 개요(아이디어 스케치)

구간 DP 기본형: dp[i][j] = min_{i≤k<j}( dp[i][k] + dp[k+1][j] ) + sum(i..j)
구간 합 sum(i..j)는 누적합으로 O(1) 계산.
이 문제의 비용 구조는 사각 부등식(Quadrangle Inequality)을 만족해 최적 분할점이 단조(모노톤)하게 이동한다. 이에 따라 크누스 최적화 적용이 가능하여 k 탐색 구간을 opt[i][j-1]..opt[i+1][j]로 줄여 전체 시간복잡도를 O(N^2)로 낮춘다.

flowchart TD
  A[파일 크기 a1..aK] --> B[누적합 prefix]
  B --> C[구간합 sum(i..j) = prefix[j]-prefix[i-1]]
  C --> D[dp[i][j] = min(dp[i][k]+dp[k+1][j]) + sum(i..j)]
  D --> E[opt[i][j] ∈ [opt[i][j-1], opt[i+1][j]]]
  E --> F[O(N^2)로 채우기]

알고리즘 설계

상태: dp[i][j] = i..j를 하나로 합치는 최소 비용, opt[i][j] = 해당 최소를 만드는 분할점 k.
점화식: 위와 동일. 길이 1 구간은 비용 0, opt[i][i]=i로 시작.
전개 순서: 구간 길이 len=2..K, 시작점 i=1..K-len+1, 끝점 j=i+len-1.
탐색 범위 축소: k ∈ [opt[i][j-1], opt[i+1][j]]만 확인.
합계 계산: sum(i..j)=prefix[j]-prefix[i-1].

복잡도

시간: O(K^2) (크누스 최적화). K=5000에서도 C++로 충분.
공간: O(K^2) — dp(8바이트) + opt(4바이트) ≈ 300MB 내외. 512MB 제한 내에서 동작.

구현 (C++)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
// 더 많은 정보는 42jerrykim.github.io 에서 확인하세요.
#include <bits/stdc++.h>
using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T; if(!(cin >> T)) return 0;
    while(T--){
        int K; cin >> K;
        vector<long long> a(K + 1), prefix(K + 1, 0);
        for(int i = 1; i <= K; ++i){
            cin >> a[i];
            prefix[i] = prefix[i - 1] + a[i];
        }

        const long long INF = (1LL << 62);
        vector<vector<long long>> dp(K + 2, vector<long long>(K + 2, 0));
        vector<vector<int>> opt(K + 2, vector<int>(K + 2, 0));
        for(int i = 1; i <= K; ++i) opt[i][i] = i;

        for(int len = 2; len <= K; ++len){
            for(int i = 1; i + len - 1 <= K; ++i){
                int j = i + len - 1;
                long long sum = prefix[j] - prefix[i - 1];
                dp[i][j] = INF;

                int L = opt[i][j - 1];
                int R = opt[i + 1][j];
                if(L > R) swap(L, R);

                for(int k = L; k <= R; ++k){
                    long long cand = dp[i][k] + dp[k + 1][j] + sum;
                    if(cand < dp[i][j]){
                        dp[i][j] = cand;
                        opt[i][j] = k;
                    }
                }
            }
        }

        cout << dp[1][K] << '\n';
    }
    return 0;
}