boj 11066: 파일 합치기

"연속된" 파일을 합쳐서 하나의 파일로 만들 때 비용이 최소일 때를 구하는 문제이다.

 

DP[i][j] = i ~ j번 파일을 합치는 최소 비용이라고 할 때,

DP[i][j] = min(DP[i][k] + DP[k+1][j]) + (A[i] ~ A[j] 까지의 합) 일 것이고 시간 복잡도는 O(N^3)이다.

 

import java.util.*;
import java.io.*;

public class Main {
	public static void main(String[] args) throws NumberFormatException, IOException {
		Scanner in = new Scanner(System.in);
		int test = in.nextInt();
		for (int t = 0; t < test; t++) {
			int n = in.nextInt();
			int page[] = new int[n + 1];
			int pageSum[] = new int[n + 1];
			for (int i = 1; i <= n; i++) {
				page[i] = in.nextInt();
				pageSum[i] = pageSum[i - 1] + page[i];
			}
			int dp[][] = new int[n + 1][n + 1];
			for (int i = 1; i <= n; i++) {
				Arrays.fill(dp[i], -1);
			}
			System.out.println(DP(dp, pageSum, 1, n));
		}
	}

	public static int DP(int dp[][], int pageSum[], int i, int j) {
		if (i == j) {
			dp[i][j] = 0;
			return dp[i][j];
		}

		if (dp[i][j] != -1) {
			return dp[i][j];
		}

		for (int k = i; k < j; k++) {
			int temp = DP(dp, pageSum, i, k) + DP(dp, pageSum, k + 1, j) + pageSum[j] - pageSum[i - 1];
			if (dp[i][j] == -1 || dp[i][j] > temp) {
				dp[i][j] = temp;
			}
		}
		return dp[i][j];
	}
}