문제

이해

N개의 파일에서 2개씩 파일을 합칠 수 있습니다. 합치는 데 필요한 비용은 각 파일의 크기입니다. 모든 파일을 합칠 때 필요한 최소 비용을 구해야 합니다.

예를 들어, 예제 1의 경우에는
1. (40 + 30) , (30 + 50) -> 150
2. 70 + 80 -> 150
총 300이 최소비용이 됩니다.

접근

우선, 완전탐색으로 생각해보면 K가 500에다가 각 테스트케이스도 존재하기 때문에 부적절해 보입니다. 따라서, 다른 방법이 필요합니다.

파일 합치기의 특징을 보면 항상 파일 2개씩 합친다는 것입니다. 뒤집어서 생각하면 항상 한 파일은 2개씩 분리되고 분리되는 기준점이 존재합니다. 기준점을 어디에 두냐에 따라서 최솟값이 달라집니다. 위에서 언급했듯이 이 기준점을 모두 탐색하는 것은 부적절합니다.

기준점을 최초에 모두 탐색한다고 생각합시다. K개의 파일이 있으면 기준점은 1부터 K-1까지 약 K번 존재합니다. 이 때의 비용은 (0 ~ i), (i ~ K)의 합으로 구성되는데 위의 2개의 분리된 파일은 다시 소문제로 분리될 수 있습니다.

여기서 DP의 아이디어를 떠올릴 수 있습니다. 문제를 소문제로 쪼갤 때 이전에 메모이제이션한 값을 사용할 수 있다면? 시간복잡도를 줄일 수 있습니다.

top-bottom 방식으로 생각해봅시다. 정답은 (0 ~ K) 파일이 됩니다. 위 파일은 다시 2개로 쪼개질 수 있습니다. 가장 작은 단위는 파일 1개로 구성되기 때문에 최소 비용을 구할 수 있습니다. 이를 다시 타고 올라가면 임의의 기준점에 대한 비용을 구할 수 있습니다. 하지만, 이 비용이 최소값을 의미하는 것은 아닙니다. 따라서, 모든 기준점에 대해서 탐색할 필요가 있습니다.

그리고 비용을 계산할 때 주의해야 할 점이 하나 있습니다. 파일의 비용은 합쳐진 두 파일의 크기의 합입니다. 하지만, 1개의 파일로 구성되는 경우에는 파일의 비용이 0입니다. 따라서, 우리는 파일의 최소비용을 구해야 하지만 그러기 위해서 분리된 파일에 대한 용량을 따로 기록해야 할 필요가 있습니다.

정리해보겠습니다.
1. 모든 기준점에 대한 파일 비용의 최솟값을 탐색하자.
2. 메모이제이션을 통해 탐색의 중복을 제거하자.
3. 분리된 파일 용량을 따로 기록하여 탐색에 사용하자.

풀이

private static int DP(int left, int right) {
        if (dpCost[left][right] != INF) {
            return dpCost[left][right];
        }

        if (left == right) {
            dpSize[left][right] = arr[left];
            return dpCost[left][right] = 0;
        }

        for (int idx = left; idx < right; idx++) {
            int file1 = DP(left, idx);
            int file2 = DP(idx + 1, right);
            int newFile = file1 + file2 + dpSize[left][idx] + dpSize[idx + 1][right];

            if (dpCost[left][right] > newFile) {
                dpCost[left][right] = newFile;
                dpSize[left][right] = dpSize[left][idx] + dpSize[idx + 1][right];
            }
        }

        return dpCost[left][right];
    }

위 코드는 DP 수행 메소드입니다.

left와 right는 파일의 합칠 범위가 되겠습니다.

dpCost 배열은 최초에 INF로 초기화되기 때문에 이후에 최솟값이 기록됐다면 바로 메소드를 빠져나옵니다.

left와 right가 같다면 해당 단위 파일을 의미하기 때문에 size를 갱신하고 0을 반환합니다.

탐색해야 하는 경우 left부터 right까지 기준점을 두어 재귀를 통해 탐색합니다. 여기서 주의해야 하는점은 새로운 파일을 만들기 위해서는 분리된 파일1의 비용과 파일2의 비용과 파일1, 2를 이루는 크기를 모두 더해야 합니다.

새롭게 만든 파일 비용이 갱신될 수 있다면 파일 비용과 크기를 갱신합니다.

반복문이 종료되면 최소가 기록된 dpCost[left][right]를 반환합니다.

코드

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

public class Main {
    static final int INF = 1_000_000_000;
    static StringTokenizer st = null;
    static StringBuilder sb = new StringBuilder();
    static int[][] dpCost;
    static int[][] dpSize;
    static int[] arr;

    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int T = Integer.parseInt(br.readLine());
        for (int test_case = 1; test_case <= T; test_case++) {
            int n = Integer.parseInt(br.readLine());
            dpCost = new int[n][n];
            for (int i = 0; i < n; i++) {
                Arrays.fill(dpCost[i], INF);
            }

            dpSize = new int[n][n];

            arr = new int[n];
            st = new StringTokenizer(br.readLine());
            for (int i = 0; i < n; i++) {
                arr[i] = Integer.parseInt(st.nextToken());
            }

            dpCost[0][n - 1] = DP(0, n - 1);
            sb.append(dpCost[0][n - 1]).append("\n");
        }

        System.out.println(sb.toString());
    }

    private static int DP(int left, int right) {
        if (dpCost[left][right] != INF) {
            return dpCost[left][right];
        }

        if (left == right) {
            dpSize[left][right] = arr[left];
            return dpCost[left][right] = 0;
        }

        for (int idx = left; idx < right; idx++) {
            int file1 = DP(left, idx);
            int file2 = DP(idx + 1, right);
            int newFile = file1 + file2 + dpSize[left][idx] + dpSize[idx + 1][right];

            if (dpCost[left][right] > newFile) {
                dpCost[left][right] = newFile;
                dpSize[left][right] = dpSize[left][idx] + dpSize[idx + 1][right];
            }
        }

        return dpCost[left][right];
    }
}

결과