[백준 11066번] 파일 합치기

문제 링크: 11066번 파일 합치기

https://www.acmicpc.net/problem/11066

 

일단 DP문제라고 하는데 왜 DP인지부터 생각해보자. 그다지 바람직하지는 않지만, 우리가 적절한 알고리즘을 고르는 데에 사용할 수 있는 판단 근거 중 하나는 주어지는 값의 범위이다. 이 문제에서는 소설을 구성하는 장의 수 K가 500 이하로서 스위핑으로 해결되기는 힘들며, O(n^2)이라고 하기에도 약간 작은 숫자이므로 O(n^3) 정도를 생각해봐야 한다는 것을 알 수 있다. 또한 "여러 장들이 연속이 되도록 파일을 합쳐나가"라는 부분에서 인접한 파일만 합쳐야 한다는 것을 알 수 있는데, 따라서 정렬이나 투 포인터 등 처리 순서가 자유로울 때에 사용할 수 있는 기법들도 여기서는 모두 후보군에서 제외해야 한다.

 

그래서, 다시 왜 DP인가?

 

아래 예시에 대해서, 파일을 합치는 여러가지 방법이 있겠지만 아래 두 가지만 생각해보자.

 

[100, 30, 50, 200, 60]

 

[100, 30, 50, 200, 60]

[130, 50, 200, 60] cost: 130

[180, 200, 60] cost: 180

[180, 260] cost: 260

[440] cost: 440

 

[100, 30, 50, 200, 60]

[100, 80, 200, 60] cost: 80

[180, 200, 60] cost: 180

[180, 260] cost: 260

[440] cost: 440

 

[180, 200, 60] 이후의 과정들은 우리가 똑같은 과정을 반복하고 있음을 알 수 있다. 잘 생각해보면, 파일을 합치는 순서에 따라 비용에는 차이가 발생하지만, 파일을 합친 결과물의 크기는 동일하기 때문에, 파일을 합쳤을 때 크기만 같다면 그 이후 과정에서는, 순서가 같은 한, 비용도 동일하게 발생한다.

이러한 반복 과정, 즉 중복된 부분 문제를 한 번만 계산하고자 하는 목적에서 memoization을 이용할 수 있는 것이다.

 

이제 DP를 사용해야 하는 것까지는 알았다. 여기서부터는 연습의 영역이라고 생각하는데, 이 문제에서는 D(i, j)를 i번째 파일부터 j번째 파일까지 합치는 데에 필요한 최소 비용이라고 정의할 수 있다. 점화식은 다음과 같다.

 

D(i, j) =

0 if i=j

A(i) + A(j) if j=i+1

min(D(i, i)+D(i+1, j), D(i, i+1)+D(i+2, j), ..., D(i, j-1)+D(j, j)) + (A[i] + A[i+1] ... + A[j]) else

 

마지막 줄에서 A[i] + A[i+1] + ... + A[j]는 왜 있을까? 이런 문제를 풀면 항상 헷갈리는 부분이 되기도 한다. D(i, j)는 i번째 파일부터 j번째 파일까지 합치는 데에 필요한 최소 비용이라고 했다. [30, 50, 100]이라는 예시에서, 1번째 파일과 2번째 파일을 먼저 합치든, 2번째 파일과 3번째 파일을 먼저 합치든, 어느 경우에든 최종적으로는 180의 비용이 마지막 단계에서 발생한다. 그렇다면 min()의 정체는? 그 이전 단계, 즉 30+50 또는 50+100의 비용이다.

 

한편, 여기서 Knuth's Optimization이라는 것을 적용해서 O(n³)을 O(n²)으로 줄일 수 있다고 한다. 하지만 코딩테스트에서 나올 범위는 아니라고 하니 접어두도록 한다. 코딩테스트를 준비하는 입장에서, 이 문제에서 최적화할 수 있는 부분은 A[i] + A[i+1] + ... + A[j]를 누적합을 통해 빠르게 구할 수 있도록 해두는 것 정도이다.

 

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

public class Main {
    static int k;
    static int[] files;
    static int[] pre;
    static int[][] dp;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int test = Integer.parseInt(br.readLine());
        while (test-- > 0) {
            k = Integer.parseInt(br.readLine());
            files = new int[k + 1];
            pre = new int[k + 1];
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            for (int i = 1; i <= k; i++) {
                pre[i] = files[i] = Integer.parseInt(st.nextToken());
            }
            for (int i = 2; i <= k; i++) {
                pre[i] += pre[i - 1];
            }

            dp = new int[k + 1][k + 1];
            for (int i = 0; i < k + 1; i++) for (int j = 0; j < k + 1; j++) dp[i][j] = -1;

            for (int i = 1; i <= k; i++) {
                for (int j = i + 1; j <= k; j++) {
                    dp[i][j] = get(i, j);
                }
            }

            sb.append(dp[1][k]).append('\n');
        }

        System.out.print(sb);
    }

    static int get(int s, int e) {
        if (s >= e) {
            return 0;
        }

        if (e == s + 1) {
            return files[s] + files[e];
        }

        if (dp[s][e] != -1) {
            return dp[s][e];
        }

        int min = Integer.MAX_VALUE;
        for (int i = s; i <= e - 1; i++) {
            int sum = get(s, i) + get(i + 1, e);
            if (sum < min) {
                min = sum;
            }
        }

        return dp[s][e] = min + pre[e] - pre[s - 1];
    }
}