[백준] 11066 파일 합치기 - Java

 

 

 

언뜻 봐서는 파일들을 정렬한 후 그리디 느낌으로 풀어낼 수 있을 것 같지만..

연속된 경우만 파일을 합칠 수 있다는 조건 때문에 그리디로는 풀 수 없다.

 

가능한 경우를 모두 탐색하는 방법은 시간이 너무 많이 걸리니.. dp를 사용해야 한다.

 

 

우선 i와 j를 설정하자. i는 시작, j는 끝을 의미하고 이차원 배열로 저장한다.

dp[i][j] 는 i에서 j까지 파일을 합칠 때 소비되는 최소 비용을 의미한다.

 

위의 배열을 잘 채워넣은 후 dp[1][j-1]의 값을 답으로 사용하자.

 

 

공통점을 찾아보자. 항상 하던대로 "마지막에 어떻게 합치는가?"를 기준으로 구분할 수 있을 것 같다.

 

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

public class Main{
	public static void main(String[] args)throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int T = Integer.parseInt(br.readLine());

		for(int start=0; start<T; start++){

			int K = Integer.parseInt(br.readLine());

			int[][] dp = new int[K+1][K+1];
			int[][] sum = new int[K+1][K+1]; // prefix sum
	
			int[] arr = new int[K+1];

			StringTokenizer st = new StringTokenizer(br.readLine());

			for(int i=1;i <K+1; i++){
				arr[i] = Integer.parseInt(st.nextToken());
			}
	
			for(int i=1; i<K+1; i++){
				for(int j=i; j<K+1; j++){
					sum[i][j] = sum[i][j-1] + arr[j];
				}
			}
	
			for(int i=2; i<K+1; i++){
				for(int j=1; j<K+1-i+1; j++){
					int k = j - 1 + i;
					dp[j][k] = Integer.MAX_VALUE;
					for(int l = j; l<k; l++){
						dp[j][k] = Math.min(dp[j][k], dp[j][l] + dp[l+1][k] + sum[j][k]);
					}
				}
			}

			// for(int a = 1; a<K+1; a++){
			// 	for(int b = 1; b<K+1; b++){
			// 		System.out.print(dp[a][b] + " ");
			// 	}
			// 	System.out.println();
			// }
	
			System.out.println(dp[1][K]);
		}
	}
}

 

 

다른 문제들과 다르게 dp배열을 채울 때 길이가 작은 순서대로 채워야 하는 부분에 주의하자.