[백준 11066번] 파일 합치기

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

 

package dp;

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

public class DP11066 {
    static int N;

    static int[] book;
    static int result;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        int T = Integer.parseInt(br.readLine());
        for (int test = 1; test <= T; test++) {
            N = Integer.parseInt(br.readLine());
            book = new int[N];
            st = new StringTokenizer(br.readLine());
            for (int i = 0; i < N; i++) {
                book[i] = Integer.parseInt(st.nextToken());
            }
            result = 0;
            solution();
            System.out.println(result);
        }
    }

    private static void solution() {
        int[] sum = new int[N + 1];
        int[][] dp = new int[N + 1][N + 1];
        for (int i = 1; i < N + 1; i++) {
            sum[i] = sum[i - 1] + book[i-1];
        }


        for (int len = 1; len < N; len++) {
            for (int i = 1; i < N - len + 1; i++) {
                int j = len + i;
                dp[i][j] = Integer.MAX_VALUE;
                for (int k = i; k < j; k++) {
                    int cost = dp[i][k] + dp[k + 1][j] + (sum[j] - sum[i - 1]);
                    dp[i][j] = Math.min(dp[i][j], cost);
                }
            }
        }

        result = dp[1][N];
    }

}

 

와 진짜 이건 너무 어려웠다.... 

 

핵심은 k를 활용해서 분할을 한 뒤 dp 배열에 각각 최솟값을 비교하면 된다! 이때 dp[i][j]가 뜻하는 거는 i번째부터 j번쨰까지라는 의미를 담고있다. 아래 사진을 통해 흐름을 이해하도록 하자.