[백준 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);
​​​​​​​​}
​​​​}
}