[백준] BOJ_11066 파일 합치기

이종찬·2026년 1월 14일

1. 문제 정보

문제 요약: 소설을 구성하는 여러 개의 장(Chapter) 파일을 합쳐서 하나의 파일로 만들어야 합니다. 두 개의 파일을 합칠 때 발생하는 비용은 두 파일 크기의 합입니다. 주어진 모든 파일을 합치는 데 필요한 최소 비용을 구하는 문제입니다. (단, 파일은 반드시 인접한 것끼리만 합칠 수 있습니다.)
난이도: Gold 3
링크: https://www.acmicpc.net/problem/11066

2. 접근 방식

1) 문제의 본질

이 문제는 언뜻 보면 작은 파일들부터 합치면 될 것 같은 '그리디(Greedy)' 문제처럼 보입니다. 하지만 인접한 파일만 합칠 수 있다는 제약 조건과, 합쳐진 파일이 다시 다른 파일과 합쳐질 때 가중치가 누적된다는 점 때문에 그리디 접근은 최적해를 보장하지 못합니다.

이 문제의 본질은 행렬 곱셈 순서(Matrix Chain Multiplication) 문제와 동일한 구간 DP (Interval DP) 유형입니다. 전체 구간 $[1, N]$ 을 합치는 최소 비용은, 이를 두 개의 부분 구간 $[1, k]$ 와 $[k+1, N]$ 으로 나누어 해결한 결과의 합 중 최솟값을 찾는 방식으로 귀결됩니다. 즉, 큰 문제를 작은 부분 문제로 나누어 푸는 최적 부분 구조(Optimal Substructure)를 가집니다.

2) 알고리즘 설계

DP 테이블을 정의하고, 바텀업(Bottom-Up) 방식으로 채워 나갑니다.

DP 정의: $DP[i][j]$ 는 $i$ 번째 파일부터 $j$ 번째 파일까지 합치는 데 드는 최소 비용입니다.
탐색 순서: 구간의 길이( $len$ )를 2부터 $N$ 까지 늘려가며 모든 가능한 시작점 $i$ 에 대해 탐색합니다.
최적화: 구간 $[i, j]$ 를 합칠 때 발생하는 비용은 항상 해당 구간의 파일 크기 총합입니다. 이를 매번 반복문으로 구하면 $O(N^4)$ 가 되어 시간 초과가 발생할 수 있으므로, 누적 합(Prefix Sum) 배열을 사용하여 $O(1)$ 에 계산해야 합니다.

3) 점화식

구간 $i$ 에서 $j$ 까지 합치는 비용은, 어떤 분기점 $k$ ( $i \le k < j$ )에서 잘랐을 때의 좌측 비용, 우측 비용, 그리고 현재 단계에서 합치는 비용(구간합)의 합입니다.

$DP[i][j] = \min_{i \le k < j} (DP[i][k] + DP[k+1][j]) + \sum_{x=i}^{j} A[x]$

여기서 $\sum_{x=i}^{j} A[x]$ 부분은 미리 계산해 둔 누적 합 배열 $S$ 를 이용해 S[j] - S[i-1]로 간단히 처리합니다.

3. 코드 구현

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static int T;
    // 최솟값 비교를 위한 초기화 값 (오버플로우 방지 주의)
    static final int INF = Integer.MAX_VALUE;

    public static void main(String[] args) throws IOException {
        T = Integer.parseInt(br.readLine());
        for (int i = 0; i < T; i++) {
            int K = Integer.parseInt(br.readLine());
            st = new StringTokenizer(br.readLine());
            int[] A = new int[K + 1];
            int[] S = new int[K + 1]; // 누적 합 배열

            for (int j = 1; j <= K; j++) {
                A[j] = Integer.parseInt(st.nextToken());
                S[j] = S[j - 1] + A[j]; // 누적 합 계산
            }

            solv(K, S);
        }
    }

    private static void solv(int n, int[] sum) {
        int[][] dp = new int[n + 1][n + 1];

        // len: 구하려는 구간의 길이 (2개부터 n개까지)
        for (int len = 2; len <= n; len++) {
            // i: 구간의 시작점
            for (int i = 1; i <= n - len + 1; i++) {
                int j = i + len - 1; // j: 구간의 끝점
                int psum = sum[j] - sum[i - 1]; // 현재 구간의 합 비용
                
                dp[i][j] = INF; // 최소값을 구하기 위해 초기화

                // k: 구간을 나누는 분기점
                for (int k = i; k < j; k++) {
                    dp[i][j] = Math.min(dp[i][j], dp[i][k] + dp[k + 1][j] + psum);
                }
            }
        }

        System.out.println(dp[1][n]);
    }
}

4. 회고 및 배운 점

1) 시간 복잡도 분석

이 알고리즘은 3중 반복문을 사용합니다.

구간의 길이 ( $O(N)$ )
구간의 시작점 ( $O(N)$ )
구간을 나누는 분기점 $k$ ( $O(N)$ )

따라서 전체 시간 복잡도는 $O(N^3)$ 입니다. $N$ 이 최대 500이므로 $500^3 = 125,000,000$ , 약 1.25억 연산입니다. 자바의 경우 1~2초 내에 충분히 통과 가능한 수치입니다. 만약 구간 합을 반복문으로 매번 구했다면 $O(N^4)$ 가 되어 시간 초과가 났을 것입니다. 누적 합(Prefix Sum)의 적용이 필수적인 이유입니다.

2) 구현 디테일

초기화 (INF): dp[i][j]를 갱신할 때 Math.min을 사용하므로, 초기값을 충분히 큰 값(Integer.MAX_VALUE)으로 설정해야 합니다.
순회 순서: DP 테이블을 채울 때 i와 j를 단순히 증가시키는 것이 아니라, 구간의 길이(len)를 기준으로 바깥 루프를 돌려야 한다는 점이 중요합니다. 작은 구간(길이 2, 3...)의 해가 먼저 구해져 있어야 큰 구간의 해를 구할 수 있기 때문입니다.

3) 트러블 슈팅

처음 문제를 접했을 때 DP의 점화식은 세웠으나, 비용 계산 부분에서 누적 합을 활용하지 않아 비효율적인 로직이 될 뻔했습니다. DP 문제에서 '구간의 합'이 빈번하게 필요할 때는 반드시 Prefix Sum을 전처리(Preprocessing) 단계에서 준비해야 함을 다시 한번 상기했습니다.