[BOJ 11066] 파일 합치기 (Java)

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

11066번: 파일 합치기

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

public class Main {
	static int T, K;
	static int[] arr;
	static int[][] dp, cost;
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st=null;
		T=Integer.parseInt(br.readLine());
		for (int t=1; t<=T; t++) {
			K=Integer.parseInt(br.readLine());
			arr=new int[K];
			dp=new int[K][K];
			cost=new int[K][K];
			st=new StringTokenizer(br.readLine());
			for (int i=0; i<K; i++) {
				arr[i]=Integer.parseInt(st.nextToken());
				dp[i][i]=arr[i];
			}
			for (int len=1; len<K; len++) {
				for (int i=0; i<K; i++) {
					int j=i+len;
					if (j>=K) break;
					int min=Integer.MAX_VALUE;
					int cmin=Integer.MAX_VALUE;
					for (int k=i; k<j; k++) {
						if (cost[i][k]+cost[k+1][j]<cmin) {
							min=dp[i][k]+dp[k+1][j];
							cmin=cost[i][k]+cost[k+1][j];
						};
					}
					dp[i][j]=min;
					cost[i][j]=dp[i][j]+cmin;
				}
			}
			System.out.println(cost[0][K-1]);
		}

	}

}

조금 복잡하게 풀었다..

 

다른 분(https://js1jj2sk3.tistory.com/3)의 코드를 보니 부분합을 이용해서

dp[i][j] => i~j까지 합치는데 드는 최소한의 비용

"dp[i][j] = min(i <= k < j){dp[i][k] + dp[k+1][j]} + psum[i][j] (psum[i][j] 는 novel[i][j] 의 i부터 j까지의 부분합)"

합치는 비용을 계산할 때 (i~j)까지의 합을 계산해주면 OK다