11066번 - 파일 합치기(dp)

문제:

 

풀이:

11049번 - 행렬곱셈순서(dp) (tistory.com)

위 문제와 매우 비슷한 문제이다.

다른점이 있다면, 계산 방식이다.

이 문제에서는 각 계산과정 발생한 합을 모두 더해서 그 최솟값을 구해야 한다.

즉, 계산과정에서 발생한 합과, 계산 결과 두가지를 dp 배열에 저장해야 한다.

직접 dp 배열을 그리며 설명하겠다.

 

먼저 파일 크기가 각각 40, 30, 30, 50이라면, 아래와 같이 시작할 수 있을 것이다.

	C1		C2		C3		C4
1개	40	0	30	0	30	0	50	0
2개
3개
4개

 

이제 파일을 2개씩 합쳐보자. C2부터 C4까지 자신보다 앞에있는 파일과 합칠 것이다.

각 행은 다시 2개로 나눈다.
앞부분엔 합쳐진 파일의 크기, 뒷부분에는 파일을 하나로 합칠때 필요한 최소 비용을 저장한다.

	C1		C2		C3		C4
1개	40	0	30	0	30	0	50	0
2개			70	70	60	60	80	80
3개
4개

 

파일 3개씩 합칠 것이다. C1~C3, C2~C4에 대한 계산을 할 것이다.

이때, 2개씩 합칠때와 달리 계산과정에 발생하는 합이 2가지 경우의 수가 나온다.

C1~C3일때는 (C1, C2) + C3 과 C1 + (C2, C3)를 비교해 봐야 할 것이고, 그 결과 표는 아래처럼 나온다.

	C1		C2		C3		C4
1개	40	0	30	0	30	0	50	0
2개			70	70	60	60	80	80
3개					100	70 + 100 VS 60 + 100
4개

계산 결과를 보면 알 수 있듯이, 파일 N개를 합한 값은 비교할 필요가 없다. 어짜피 같은 결과가 나온다.

비교가 필요한 값은 파일을 하나로 합칠때 필요한 비용이다.

C2 ~ C4까지 계산했을 때 dp는 아래와 같이 저장될 것이다.

	C1		C2		C3		C4
1개	40	0	30	0	30	0	50	0
2개			70	70	60	60	80	80
3개					100	70 + 100 VS 60 + 100 =160	110	60 + 110 VS 80 + 110 =170
4개

마지막으로 파일 4개를 모두 합쳐볼 것이다.

DP 배열을 이용해 계산 과정 발생하는 최솟값을 미리 저장해놓았으니, 그것을 이용하면 된다.

비교해야할 계산 과정은 (C1~C3)+C4 VS (C1~C2)+(C3~C4) VS C1+(C2~C4) 이다.

DP는 아래와 같이 작성된다.

	C1		C2		C3		C4
1개	40	0	30	0	30	0	50	0
2개			70	70	60	60	80	80
3개					100	160	110	170
4개							150	160 + 150 VS 70 + 80 + 150 VS 170 + 150 = 300

 

위 계산 과정을 토대로 코드를 짜자면, 주요 부분은 다음과 같이 작성해야 할 것이다.

이해에 가장 중요한 부분은 마지막 파일 4개를 합치는 부분이다.

 

4개의 파일을 1:3, 2:2, 3:1로 나눠 파일을 하나로 합칠때 필요한 최소 비용을 구했다.

합쳐야할 파일의 개수를 n이라고 했을때 n-1:1 ~ 1:n-1 까지 비교하는 것이다.

각각의 값은 dp 배열에 저장되어 있으므로, 계산하기 어렵지 않다.

 

그 결과 나온 메서드는 아래와 같다.

static void minCost(int K, int[][][] dp) {
    for (int fileNum = 2; fileNum <= K; fileNum++) { // 파일 묶음의 수
        for (int start = fileNum; start <= K; start++) { // 비교 시작점
            int sum = dp[1][start-fileNum+1][0] + dp[fileNum-1][start][0]; // 새로 더해질 값
            dp[fileNum][start][0] = sum;
            for (int i = 1; i < fileNum; i++) { // i : fileNum-i로 파일 묶음을 나눔
                int tot = dp[i][start-fileNum+i][1] + dp[fileNum-i][start][1]; // 이전까지 계산한 값
                if (dp[fileNum][start][1] > tot + sum) {
                    dp[fileNum][start][1] = tot + sum;
                }
            }
        }
    }
}

두번째 start 반복문이 이해가 안되면, 파일을 2개씩 또는 3개씩 합칠때 과정을 살펴보고 오면 이해 될 것이다.

dp 배열이 3차원인 이유는 dp[][][0]에는 합쳐진 파일의 크기, dp[][][1]에는 파일을 하나로 합칠때 필요한 최소 비용이다.

dp[K][K][1]에 저장되어 있는 값이 파일을 하나로 합칠때 필요한 최소 비용이다.

 

전체코드:

import java.util.*;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int T = sc.nextInt();
        int[] output = new int[T];

        for (int i = 0; i < T; i++) {
            int K = sc.nextInt();
            int[][][] dp = new int[K+1][K+1][2];
            for (int j = 2; j <= K; j++) {
                for (int k = 0; k <= K; k++) {
                    Arrays.fill(dp[j][k], Integer.MAX_VALUE);
                }
            }

            for (int j = 1; j <= K; j++) {
                dp[1][j][0] = sc.nextInt();
            }

            minCost(K, dp);
            output[i] = dp[K][K][1];
        }

        for (int i = 0; i < T; i++) { // 결과 출력
            System.out.println(output[i]);
        }
    }

    static void minCost(int K, int[][][] dp) {
        for (int fileNum = 2; fileNum <= K; fileNum++) { // 파일 묶음의 수
            for (int start = fileNum; start <= K; start++) { // 비교 시작점
                int sum = dp[1][start-fileNum+1][0] + dp[fileNum-1][start][0]; // 새로 더해질 값
                dp[fileNum][start][0] = sum;
                for (int i = 1; i < fileNum; i++) { // i : fileNum-i로 파일 묶음을 나눔
                    int tot = dp[i][start-fileNum+i][1] + dp[fileNum-i][start][1]; // 이전까지 계산한 값
                    if (dp[fileNum][start][1] > tot + sum) {
                        dp[fileNum][start][1] = tot + sum;
                    }
                }
            }
        }
    }
}

 

시행착오:

그동안 dp 골드 문제가 꽤나 어렵게 느껴졌는데, 이번에는 빠르게 풀 수 있었다.

11049번 - 행렬곱셈순서(dp) (tistory.com)

11049번 - 행렬곱셈순서(dp)

이 문제를 풀며 블로그에 한번 더 작성해, 문제 자체를 더 자세하게 이해했기 때문일 것이다.

 

블로그를 작성하며 비슷한 문제를 다시 틀릴 가능성이 줄어들고 있는 것같다:)