[BOJ/DP] 백준 11066 - 파일 합치기 (Java)

백준 11066 - 파일 합치기

https://www.acmicpc.net/problem/11066

문제

소설을 여러 장으로 나누어 쓰는데, 각 장은 각각 다른 파일에 저장
소설의 모든 장을 쓰고 나서 각 장이 쓰여진 파일을 합쳐서 최종적으로 소설의 완성본이 들어있는 한 개의 파일 만듦
이 과정에서 두 개의 파일 합쳐서 하나의 임시 파일 만들고,임시 파일이나 원래의 파일을 계속 두 개씩 합쳐서 소설의 여러 장들이 연속이 되도록 파일을 합쳐나가고, 최종적으로 하나의 파일로 합침
두 개의 파일을 합칠 때 필요한 비용이 두 파일 크기의 합

입력: T개의 테스트로 이뤄져 있고 T는 입력의 맨 첫 줄에 주어짐
각 테스트 데이터는 두 개의 행으로 주어짐
첫 행: 소설을 구성하는 장의 수 K (3 <= K <= 500)
두 번째 행: 1장 ~ K장까지 수록한 파일의 크기를 나타내는 K (< 10,00)
출력: 모든 장을 합치는데 필요한 최소 비용

---

풀이

• `prefix[i]`: 1번부터 i번까지의 합
• `dp[i][j]`:i번 파일부터 j번 파일까지 합치는 최소 비용

long cost = dp[i][k] + dp[k + 1][j] + (prefix[j] - prefix[i - 1]);
dp[i][j] = Math.min(dp[i][j], cost);

---

코드

import java.io.*;
import java.util.*;

// 파일 합치기
public class boj_11066 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        int T = Integer.parseInt(br.readLine());
        while (T-- > 0) {
            int K = Integer.parseInt(br.readLine());

            int[] arr = new int[K + 1];
            int[] prefix = new int[K + 1];
            long[][] dp = new long[K + 1][K + 1];

            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int i = 1; i <= K; i++) {
                arr[i] = Integer.parseInt(st.nextToken());
                prefix[i] = prefix[i - 1] + arr[i];
            }

            for (int len = 2; len <= K; len++) {
                for (int i = 1; i + len - 1 <= K; i++) {
                    int j = i + len - 1;
                    dp[i][j] = Long.MAX_VALUE;

                    for (int k = i; k < j; k++) {
                        long cost = dp[i][k] + dp[k + 1][j] + (prefix[j] - prefix[i - 1]);
                        dp[i][j] = Math.min(dp[i][j], cost);
                    }
                }
            }

            sb.append(dp[1][K]).append('\n');
        }

        System.out.println(sb);
    }
}