[백준 11066번] 파일 합치기

문제 링크: 11066번 제목

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

 

앞서 행렬의 곱 문제와 유사하다. 부분 문제의 해를 2차원 배열에 저장한다. 다만 여기서는 한 개짜리 파일을 두 개 합칠 때와 그렇지 않을 때의 계산 과정이 달라진다.

 

merge_cost(A, B) = A.size + B.size
merge_cost(AB, C) = merge_cost(A, B) + merge_cost(C) + size(AB) + size(C)

 

이를 고려하여 dp[i][1]과 dp[i][2]를 모두 미리 채운 후 dp 배열을 채워나간다.

 

import java.util.Arrays;
import java.util.Collections;
import java.util.Scanner;
import java.util.ArrayList;

public class Main {
    static int[] partialSum;
    
    public static int size(int i, int j) {
        return partialSum[i] - partialSum[i-j];
    }

    public static void solution(int[] arr, int n) {
        // create partialSum
        partialSum = Arrays.copyOf(arr, n+1);
        for (int i = 2; i <= n; i++)
            partialSum[i] += partialSum[i-1];

        // create dp
        int[][] dp = new int[n+1][n+1];

        for (int i = 2; i <= n; i++)
            dp[i][2] = size(i, 2);

        for (int i = 3; i <= n; i++) {
            for (int j = 3; j <= i; j++) {
                ArrayList<Integer> list = new ArrayList<>();
                int min = Integer.MAX_VALUE;
                for (int t = 1; t <= j-1; t++) {
                    int cur = dp[i-j+t][t] + dp[i][j-t];
                    if (cur < min)
                        min = cur;
                }
                dp[i][j] = min + size(i, j);
            }
        }

        System.out.println(dp[n][n]);
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int testCases = sc.nextInt();
        for (int testCase = 0; testCase < testCases; testCase++) {
            int n = sc.nextInt();
            int[] arr = new int[n+1];
            for (int i = 1; i <= n; i++)
                arr[i] = sc.nextInt();
            solution(arr, n);
        }
    }
}