백준 11066 파일 합치기 Java: 누적합과 구간 DP 점화식

백준 11066번 ‘파일 합치기’는 순서대로 놓인 파일을 인접한 것끼리 합쳐 하나로 만들 때 최소 비용을 구한다. 어떤 구간을 마지막에 두 덩어리로 합친다고 생각하면 두 하위 구간의 최소 비용과 전체 구간 크기로 점화식을 만들 수 있다.

• 백준 11066번 파일 합치기

DP 상태와 마지막 합치기

dp[start][end]를 start번부터 end번 파일까지 하나로 만드는 최소 비용이라고 하자. 마지막 단계에서 middle을 기준으로 왼쪽과 오른쪽 파일을 합친다면 다음 비용이 든다.

dp[start][middle]
+ dp[middle + 1][end]
+ sum(start..end)

마지막 두 덩어리의 크기를 합친 값은 원래 start..end 파일 전체 크기와 같다. 모든 middle을 시도해 최솟값을 택한다.

dp[start][end]
= min(dp[start][middle] + dp[middle+1][end])
  + prefix[end] - prefix[start-1]

구간 합을 매번 다시 더하지 않도록 prefix sum을 만든다.

Java 코드

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

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader reader = new BufferedReader(
                new InputStreamReader(System.in)
        );
        int testCount = Integer.parseInt(reader.readLine());
        StringBuilder output = new StringBuilder();

        for (int test = 0; test < testCount; test++) {
            int fileCount = Integer.parseInt(reader.readLine());
            long[] prefix = new long[fileCount + 1];
            StringTokenizer tokenizer = new StringTokenizer(
                    reader.readLine()
            );

            for (int file = 1; file <= fileCount; file++) {
                prefix[file] = prefix[file - 1]
                        + Long.parseLong(tokenizer.nextToken());
            }

            long[][] dp = new long[fileCount + 1][fileCount + 1];

            for (int length = 2; length <= fileCount; length++) {
                for (
                        int start = 1;
                        start + length - 1 <= fileCount;
                        start++
                ) {
                    int end = start + length - 1;
                    long rangeSum = prefix[end] - prefix[start - 1];
                    dp[start][end] = Long.MAX_VALUE;

                    for (int middle = start; middle < end; middle++) {
                        dp[start][end] = Math.min(
                                dp[start][end],
                                dp[start][middle]
                                        + dp[middle + 1][end]
                                        + rangeSum
                        );
                    }
                }
            }

            output.append(dp[1][fileCount]).append('\n');
        }

        System.out.print(output);
    }
}

계산 순서와 복잡도

dp[start][end]를 구할 때 더 짧은 두 구간의 답이 필요하므로 구간 길이를 2부터 늘린다. 한 파일은 이미 하나로 합쳐진 상태이므로 대각선 dp[i][i]는 기본값 0이다.

• 구간 수: O(K²)
• 구간별 분할점 탐색: O(K)
• 전체 시간: O(K³)
• DP와 prefix 공간: O(K²)

문제의 현재 제한에서는 이 풀이로 충분하다. 더 큰 제약에서는 Knuth optimization 조건을 검토할 수 있지만, 먼저 기본 점화식과 적용 조건을 분리해 이해해야 한다.

일주일 동안 붙잡았던 기록

원문에는 아이디어는 떠올렸지만 맞는지, 어떻게 code로 옮길지 감이 오지 않아 약 일주일을 붙잡다가 검색의 도움을 받아 풀었다고 적혀 있다. 네 파일의 여러 합치기 순서를 손으로 전개하면서 각 파일이 비용에 몇 번 포함되는지도 비교했다.

결정적인 단순화는 “모든 합치기 순서를 한꺼번에 나열”하는 대신 마지막 분할점 하나를 고르고 양쪽의 최적해를 재사용하는 것이다. 구간 전체 합은 어느 분할점을 골라도 마지막에 한 번 더해지므로 prefix sum으로 분리할 수 있다.

당시 두 구현의 제출 시간 804ms와 956ms도 함께 기록했다. 한 번의 online judge 수치는 runtime 상태와 JVM warm-up 같은 조건을 통제한 benchmark가 아니므로, 두 점화식 형태의 일반적인 성능 차이라고 해석하지는 않는다.

같은 구간 DP에서 마지막 비용이 행렬 차원 곱으로 바뀌는 문제는 백준 11049 행렬 곱셈 순서에서 이어진다.

검증 범위

Java source를 수동 검토하고 파일 1개, 2개, 공식 예제와 작은 random file sequence를 모든 인접 merge 순서를 열거하는 oracle과 대조한다. 현재 환경에는 실제 JDK가 없어 compile·judge 재제출은 live 반영 전에 별도 확인이 필요하다.