[BOJ]11066 - 파일 합치기(G3)

문제 링크

11066-파일 합치기

---

입력

프로그램은 표준 입력에서 입력 데이터를 받는다.
프로그램의 입력은 T개의 테스트 데이터로 이루어져 있는데, T는 입력의 맨 첫 줄에 주어진다.

각 테스트 데이터는 두 개의 행으로 주어지는데,
첫 행에는 소설을 구성하는 장의 수를 나타내는 양의 정수 K (3 ≤ K ≤ 500)가 주어진다.
두 번째 행에는 1장부터 K장까지 수록한 파일의 크기를 나타내는 양의 정수 K개가 주어진다.
파일의 크기는 10,000을 초과하지 않는다.

출력

프로그램은 표준 출력에 출력한다. 각 테스트 데이터마다 정확히 한 행에 출력하는데,
모든 장을 합치는데 필요한 최소비용을 출력한다.

---

문제 풀이

• dp[i][j]는 i번 페이지부터 j번 페이지까지의 최소 비용
• sumList[i]는 i번 페이지까지 파일 크기의 합

그럼 dp[i][i+2] 즉, i번부터 i+2번 페이지까지의 합의 최솟값은 어떻게 될까?
dp[i][i] + dp[i+1][i+2] + (files[i] + files[i + 1] + files[i + 2]) 과
dp[i][i+1] + dp[i + 2][i + 2] + (files[i] + files[i + 1] + files[i + 2]) 중 최솟값이다.

위와 같은 식으로 점화식을 일반화해서 생각해보면
m이 (i,j) 구간 내의 어느 한 점을 의미할 때

dp[i][j] = dp[i][m] + dp[m+1][j] + sum(i,j)

그리고 페이지를 묶어야하기 때문에 두장씩, 세장씩 묶는 과정이 필요한데
이를 통해 아래와 같은 3차원 반복문을 이끌어낼 수 있다.

for (int j = 2; j < k; j++) // 몇장을 묶을 것인가?
                for (int i = 0; i + j < k; i++) // 어디서부터 묶기 시작할 것인가?
                    for (int m = i; m < i + j; m++) // 범위가 주어졌을 때 특정 지점으로 나눠가며 모든 경우의 수를 확인해 최소값구하기

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

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

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        StringBuilder sb = new StringBuilder();
        int t = Integer.parseInt(br.readLine());

        while (t-- > 0) {
            k = Integer.parseInt(br.readLine());
            files = new int[k];
            sumList = new int[k];

            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < k; j++) {
                files[j] = Integer.parseInt(st.nextToken());
            }
            
            // sum배열 초기화
            sumList[0] = files[0];
            for (int s = 1; s < k; s++) {
                sumList[s] = sumList[s - 1] + files[s];
            }

			// dp배열 초기화
            // dp[i][[i] = files[i]
			// dp[i][[i+1] = files[i] + files[i+1]
            dp = new int[k][k];
            for (int i = 0; i < k-1; i++) {
                dp[i][i + 1] = files[i] + files[i + 1];
            }

            for (int j = 2; j < k; j++) {
                for (int i = 0; i + j < k; i++) {
                    dp[i][i + j] = Integer.MAX_VALUE;
                    for (int m = i; m < i + j; m++) {
                        dp[i][i + j] = Math.min(dp[i][i + j], dp[i][m] + dp[m + 1][i + j] + sum(i, i + j));
                    }
                }
            }

            sb.append(dp[0][k-1]);
            sb.append("\n");
        }
        System.out.println(sb);

    }

    static int sum(int start, int end) {
        if(start ==0 ) return sumList[end];
        return sumList[end] - sumList[start - 1];
    }
}

이 문제는 엄청 오랜시간 붙잡고 있었고,
해설들을 찾아봐도 이해하는데 많은 시간이 걸렸다.
근데 다시 생각해보면 뭐 그렇게 어려운 문제는 아닌거 같기도..?
그냥 dp문제들은 다 풀고나면 쉬워보이는 것 같다.

더 자세하게 풀이과정을 적고 싶었지만
이해하는 것과 풀이과정을 정리하는건 너무 다른 일이라 어렵다..

<참고한 글들>
소스 코드를 기록하는 남자
DevBee