[TIL] 막혔던 문제 - 백준 11066번 풀이

1. 막히게 된 문제

다이나믹 프로그래밍(DP)에 익숙해졌다고 생각했지만 골드3 티어의 문제를 풀기에는 아직 부족했던 것 같습니다
문제 접근에도 어려움이 있었고 해설을 보면서 해석하는 것도 힘들었지만 TIL로 정리하면서 풀어보겠습니다

• 백준 11066번 - 파일 합치기

문제에 “파일을 계속 두 개씩 합쳐서 소설의 여러 장들이 연속이 되도록 파일을 합쳐나가고“를 놓치면 안됩니다
이걸 지나쳐버려서 몇 시간동안 삽질했었네요

---

2. 문제 접근

우선 값을 계속 더하면서 최소 비용을 구하는 문제이기 때문에 “누적합”을 사용하는 것을 인지해두고..

단계별로 진행할 때마다 파일 크기를 2개씩 합쳐야 합니다
{ 40, 30, 30, 50 }이 있으면 { (40 + 30), (30 + 50) } 또는 { 40, (30 + 30), 50 }일 수도 있구요

1단계는 단순히 파일 2개를 합치기에 한 가지 방법만 있습니다 -> f1+f2
2단계는 파일을 3개 합치기 때문에 두 가지 방법이 있습니다 -> (f1+f2)+f3, f1+(f2+f3)

하지만 3단계가 되면서부터는 점점 경우의 수가 늘어납니다

1. F1+(F2+(F3+F4))
2. (F1+F2)+(F3+F4)
3. ((F1+F2)+F3)+F4

패턴을 보면 두 개의 묶음의 합으로 알아볼 수 있습니다

3단계에서는 [ F1+(F2~F4), (F1~F2)+(F3~F4), (F1~F3)+F4 ] 이렇게 볼 수 있습니다
4단계부터도 [ F1+(F2~F5), (F1~F2)+(F3~F5), … ]가 되는 것을 알 수 있구요

그러면 DP에 작은 조합의 최소 비용부터 저장해나가며 문제를 풀면 되겠습니다

---

3. 문제 풀이

dp[A][B]를 사용해보겠습니다
A는 파일의 시작 위치, B는 파일의 끝 위치로 정해서 ‘A ~ B’의 최소 비용이라고 정의하겠습니다

이제 dp[A][B]에 값을 각각 저장하기 위해 3중 for문을 사용해야 합니다

for (int cnt = 1; cnt < K; cnt++) {         // 합칠 파일의 개수
    for (int s = 0; s < K-cnt; s++) {       // 합칠 파일의 시작 위치 (0번째 파일부터)
        for (int i = s; i < s+cnt; i++) {   // 두 묶음으로 나눌 분기점 위치
        // dp[s][s+cnt] = Math.min(dp[s][s+cnt], (위치 i에서 나뉘어진 두 묶음의 비용 합));
        }
    }
}

분기점 위치(i)에 따라 두 묶음의 비용의 합이 달라지기 때문에 이 중에서 최솟값을 구해야 합니다

나뉘어진 두 묶음의 비용은 dp[s][i], dp[i+1][s+cnt]가 되고
여기에 중복으로 더해지는 값은 범위 내에 있는 파일의 누적합이 됩니다

예를 들어, { (30 + 40) + 50 }이 최소 비용이면 dp에는 ( 30 + 40 )이 두 번 더해집니다
그렇기에 범위에 있는 한 번 더 더해줘야 하며, 하나의 파일만 있는 경우(50)는 중복으로 더할 필요가 없습니다

따라서, 여기서 알 수 있는건 다음 2가지가 되겠습니다

1. 0부터 n까지의 누적합 sum[] 배열 선언 필요
2. 한 가지 파일만 있는 묶음은 중복합이 필요X -> dp[n][n] = 0; 대입

마지막으로 ‘(위치 i에서 나뉘어진 두 묶음의 비용 합)’까지 계산해주면 문제 풀이는 끝이 납니다

import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

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

        for (int t = 1; t <= T; t++) {
            int K = Integer.parseInt(br.readLine());

            int[][] dp = new int[K][K];     // dp[a][b]에 대해 파일 a~b의 비용의 합을 저장할 배열
            int[] sum = new int[K];         // 0부터 n 까지의 누적합을 저장할 배열

            // 34번째 줄의 Math.min에 사용할 dp[s][s+cnt]의 디폴트가 0인 경우 정상 작동 X
            for (int[] row : dp)
                Arrays.fill(row, Integer.MAX_VALUE);

            st = new StringTokenizer(br.readLine());
            for (int n = 0; n < K; n++) {
                int num = Integer.parseInt(st.nextToken());
                sum[n] = (n == 0) ? num : num + sum[n - 1];     // 누적합 저장
                dp[n][n] = 0;                                   // 파일이 1개일 때에는 중복 계산이 필요 없으므로 0 대입
            }

            for (int cnt = 1; cnt < K; cnt++) {         // 합칠 파일의 개수
                for (int s = 0; s < K-cnt; s++) {       // 합칠 파일의 시작 위치
                    for (int i = s; i < s+cnt; i++) {   // 두 묶음으로 나눌 분기점
                        dp[s][s+cnt] = Math.min(dp[s][s+cnt], dp[s][i] + dp[i+1][s+cnt] + sum[s+cnt] - (s == 0 ? 0 : sum[s-1]));
                        // sum[s+cnt] - sum[s-1] : 중복으로 더해지는 s부터 (s+cnt)까지의 비용 합
                        // 단, s == 0이면 sum[s-1]을 참조할 수 없으므로 삼항연산자 사용
                    }
                }
            }

            // 결론적으로 모든 파일의 합을 구하는 dp[0][K-1]을 출력하면 됨
            bw.write(dp[0][K-1]+"\n");
        }

        bw.flush();

        br.close();
        bw.close();
    }
}