백준 11066번 : 파일합치기[java]

dp[i][j]는 i번 파일부터 j번 파일을 합치는데 든  최소비용이다.

dp[i][i]는 chapter[i]이고,

dp[i][i+1]은 chapter[i] + chapter[i+1] = sum[i] - sum[i-1]이다.

dp[i][i+2]부턴 i과 i+1번을 합친 후 i+2번을 합치기, i+1번과 i+2번을 합친 후 i번을 합치기 중 선택해야 한다.

이를 식으로 나타내면,

dp[i][i] + dp[i+1][i+2] + (sum[i+2] - sum[i-1])  와  dp[i][i+1] + dp[i+2][i+2] + (sum[i+2] - sum[i-1]) 중 더 작은 수가 dp[i][i+2]이다.

sum[i+2] - sum[i-1]은 현재 합치려는 파일 2개를 합치는데 사용하는데 드는 비용이다.

여기서 from과 to사이의 임의의 번호인 div ( from <= div <= to )를 사용해서 dp[from][to]를 나타낼 수 있다.
dp[from][to] = dp[from][div] + dp[div+1][to] + sum[to] - sum[from-1]으로 나타낼 수 있고,

(sum[to] - sum[from-1]도 마찬가지로 dp[from][div]파일과 dp[div+1][to] 파일을 합치는데 드는 비용이다.)
dp[from][to]가 최솟값이 되는 div는 div를 바꿔가며 반복문을 통해 구할 수 있다.

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

public class Main{
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;
        
        int T = Integer.parseInt(br.readLine());
        
        // 테스트케이스 반복
        while(T-->0) {
        	int k = Integer.parseInt(br.readLine());
        	int[] chapter = new int[k+1]; // 각 장(chapter)의 크기
        	int[] sum = new int[k+1]; // 1번부터 i번까지 chapter의 합
        	int[][] dp = new int[k+1][k+1]; // dp[from][to] : from부터 to까지 합칠 때의 최솟값
        	
        	st = new StringTokenizer(br.readLine());
        	for(int i=1; i<=k; i++) {
        		chapter[i] = Integer.parseInt(st.nextToken());
        		sum[i] = sum[i-1]+chapter[i];
        	}
   	
        	// n은 from과 to사이의 간격(from+n = to)
        	for(int n=1; n<k; n++) {
        		for(int from=1; from+n <=k; from++) {
        			int to = from+n;
        			dp[from][to] = Integer.MAX_VALUE;
        			// from부터 to 사이의 모든 div를 검사하여 최솟값을 찾는다.
        			for(int div= from; div<to; div++) {
        				dp[from][to] = Math.min(dp[from][to], dp[from][div] + dp[div+1][to] + (sum[to] - sum[from-1]));
        			}
        		}
        	}
        	System.out.println(dp[1][k]);
        }
    }
}