백준 11066번

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

11066번: 파일 합치기

 

풀이

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

public class Main {
    private static final BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
    private static final StringBuilder stringBuilder = new StringBuilder();

    public static void main(String[] args) throws Exception {
        int t = Integer.parseInt(bufferedReader.readLine());

        while (t-- > 0) {
            int k = Integer.parseInt(bufferedReader.readLine());
            int[] prefixSum = new int[k + 1];
            int[] inputArr = new int[k + 1];

            StringTokenizer stringTokenizer = new StringTokenizer(bufferedReader.readLine(), " ");
            int index = 1;

            while (stringTokenizer.hasMoreTokens()) {
                int input = Integer.parseInt(stringTokenizer.nextToken());
                inputArr[index] = input;

                if (index == 0) {
                    prefixSum[index] = input;
                } else {
                    prefixSum[index] = input + prefixSum[index - 1];
                }
                index++;
            }

            int[][] dp = new int[k + 1][k + 1];

            for (int i = 1; i <= k; i++) {
                int idx = 1;
                for (int j = i; j <= k; j++) {
                    if (idx == j) {
                        dp[idx][j] = inputArr[idx];
                    } else if (j - idx == 1) {
                        dp[idx][j] = dp[idx][j - 1] + dp[idx + 1][j];
                    } else {
                        int min = Integer.MAX_VALUE;
                        for (int m = idx; m <= j - 1; m++) {
                            if (m == idx) {
                                min = Math.min(min, dp[idx][m] + dp[m + 1][j] + prefixSum[j] - prefixSum[idx]);
                            } else if (m == j - 1) {
                                min = Math.min(min, dp[idx][m] + dp[m + 1][j] + prefixSum[j - 1] - prefixSum[idx - 1]);
                            } else {
                                min = Math.min(min, dp[idx][m] + dp[m + 1][j] + prefixSum[j] - prefixSum[idx - 1]);
                            }
                        }
                        dp[idx][j] = min;
                    }
                    idx++;
                }
            }

            stringBuilder.append(dp[1][k]).append("\n");
        }

        System.out.println(stringBuilder);
    }
}