백준 11066 파일 합치기 (Gold 3)

문제 설명

전략

• 파일 합치기 문제는 BST 병합 문제와 비슷하다. 왼쪽, 오른쪽으로 나눠서 병합하여 하나의 노드로 만드는 문제

• 파일을 합치는 과정을 진행할 때 다음 3가지를 고려해야한다

  • 1. 몇 개를 묶어서 1단계로 병합할 것인가?
  • 2. 어떤 파일부터 병합할 것인가?
  • 3. 묶은 파일 집합의 2개의 부분집합을(left, right) 어떻게 나눌것인가? (pivot)

• DP[start][end]에는 start에서 end 번호를 가진 파일을 묶을 때 가장 작은 값을 업데이트 해준다

• 그럼 모든 구간에 대해서 합치는 경우의 최솟값이 나오게 되고 DP[1][END]를 구하면 1번에서 end 번호까지 합치는 최솟값을 구할 수 있다

정답코드

package algorithms;

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

public class MergeFile {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int TC = Integer.parseInt(st.nextToken());

		for (int t = 0; t < TC; t++) {
			int[] file; 
			int[] SumFile;
			int[][] dp;
			
			st = new StringTokenizer(br.readLine());
			int K = Integer.parseInt(st.nextToken());
			
			file = new int[K+1];
			SumFile = new int[K+1];
			dp = new int[K+1][K+1];

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

			// file 병합에 걸리는 시간, 누적합 초기화
			for (int i = 1; i < K + 1; i++) {
				file[i] = Integer.parseInt(st.nextToken());
				SumFile[i] = SumFile[i-1]+file[i];
			}
			
			
			//몇 장씩 묶어서 merge 할 건지
			for(int n = 1; n <= K; n++) {		
				//시작 지점을 한칸 씩 옮겨가면서 
				for(int start = 1; start+n<=K; start++) {
					int end = start+n; //끝지점 정하기
					dp[start][end] = Integer.MAX_VALUE;				
					
					//파일을 합칠 구간에서도 left와 right로 나누어서 병합해줘야한다 
					for(int divide = start; divide < end; divide++) {
						dp[start][end] = Math.min(dp[start][end], 
										 dp[start][divide] + dp[divide+1][end] + SumFile[end]-SumFile[start-1]);
					}
				}
			}
		
			System.out.println(dp[1][K]);
			
		}
	}
}