백준 11066번 - 파일 합치기

문제

백준 11066번 - 파일 합치기

아이디어

• dp[s][e]를 s ~ e구간의 최소비용이라 가정한다.
• 예제 1을 기준으로 1~4 구간의 최소비용을 구하려면 다음과 같은 경우의 수가 있다.

1. dp[1][1] + dp[2][4] => 2~4번 합치고 1번 합치기
2. dp[1][2] + dp[3][4] => 1~2번 합치고 3~4번 합치고 둘이 합치기
3. dp[1][3] + dp[4][4] => 1~3번 합치고 4번 합치기

• s와 e가 같은 경우, 즉 같은 파일을 합치는 경우는 비용이 0이다.
• 2~4번 합치는 경우는 또 dp[2][2] + dp[3][4]와 dp[2][3] + dp[4][4]가 존재하므로 탑다운 방식으로 재귀호출을 이용해 해결할 수 있다.
• 그리고 2~4번 전체를 합치는 비용도 계산해야 한다. 그런데 이렇게 2칸 이상의 구간을 합치는 경우는 DP 과정동안 반복적으로 일어날 것이다.
• 매번 반복문으로 계산할수도 있지만 당연히 비효율적이다. 그래서 누적합 배열을 따로 구해준다. 누적합 배열의 특징을 활용하여 특정 구간의 누적합을 쉽게 구할 수 있다.

예상 시간 복잡도

• 테스트 케이수 개수 : T
• 소설을 구성하는 장의 수 : N
• 예상 시간 복잡도 : O(T x N^2)

코드 구현

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

public class BJ_11066 {

    static int[] sum;
    static int[][] dp;

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int t = Integer.parseInt(br.readLine());

        while (t-- > 0) {

            int k = Integer.parseInt(br.readLine());

            sum = new int[k + 1]; //누적합
            dp = new int[k + 1][k + 1];

            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int i = 1; i <= k; i++) {
                sum[i] = sum[i - 1] + Integer.parseInt(st.nextToken());
                Arrays.fill(dp[i], -1);
            }

            System.out.println(solve(1, k));
        }
    }

    private static int solve(int s, int e) {
        if (s == e) {
            return dp[s][e] = 0;
        }
        if (dp[s][e] != -1) {
            return dp[s][e];
        }

        dp[s][e] = Integer.MAX_VALUE;
        //중간을 바꿔가면서 합한 값과 전체 구간의 비용을 더한다.
        for (int m = s; m < e; m++) {
            int temp = solve(s, m) + solve(m + 1, e) + sum[e] - sum[s - 1];
            dp[s][e] = Math.min(dp[s][e], temp);
        }

        return dp[s][e];
    }
}