아이디어

• 문제가 최적 부분문제의 형태를 가진다. DP를 적용한다고 생각하고 점화식을 생각해보자.
• 구하고자 하는 것은 1~K번을 모두 합치는 '최소 비용'이다.
  • i~j번을 모두 합쳤을 때의 최소 비용을 cost[i][j]라 하자.
  • 한편, 그렇게 합쳤을 때의 파일 크기를 size[i][j]라 하면, i ≤ k < j에 대해

    cost[i][j] = min((cost[i][i+k] + cost[k+1][j]) + (size[i][k] + size[k+1][j]))

    이 되고, 그때의 size[i][j]는 오른쪽 size의 합 부분이다.
  • 이때 구하는 값은 cost[1][K]다.
• 이러한 방식의 풀이는 $O(n^3)$의 시간복잡도를 갖는다. $n \leq 500$이므로 충분할 것 같다.

코드

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

public class Main {
	static BufferedReader rd = new BufferedReader(new InputStreamReader(System.in));
	static StringBuilder sb = new StringBuilder();
	static StringTokenizer tk = null;

	static int T, K;	
	static int[][] size, cost;
	
	public static void main(String[] args) throws Exception {
		T = Integer.parseInt(rd.readLine());
		for (int t=1; t<=T; t++) {
			K = Integer.parseInt(rd.readLine());
			
			size = new int[K+1][K+1];
			tk = new StringTokenizer(rd.readLine());
			for (int i=1; i<=K; i++) {
				size[i][i] = Integer.parseInt(tk.nextToken());
			}
			cost = new int[K+1][K+1];
			
			for (int i=1; i<K; i++) {
				// memo[j][j+i]
				for (int j=1; j<=K-i; j++) {
					cost[j][j+i] = Integer.MAX_VALUE;
					for (int k=j; k<j+i; k++) {
						int newSize = size[j][k] + size[k+1][j+i];
						int newCost = cost[j][k] + cost[k+1][j+i] + newSize;
						if (newCost < cost[j][j+i]) {
							size[j][j+i] = newSize;
							cost[j][j+i] = newCost;
						}
					}
				}
			}
			
			sb.append(cost[1][K]).append('\n');
		}
		
		System.out.println(sb);
	}
}

메모리 및 시간

• 메모리: 34072 KB
• 시간: 812 ms

리뷰

• 2차원 배열을 2차원적으로 생각하지 않는 것도 방법이다. 이 문제에서는 변수가 2개(시작 범위, 끝 범위)인 함수처럼 생각하는 것이 좋다.
• DP의 Memoization은 구해야 할 값을 명확히 해야 한다. 나의 경우 비용이 '크기의 합'과 같다고 착각하여 많은 디버깅을 해야 했다.