[백준(Baekjoon)][자바(java)] 11066 : 파일 합치기 / 동적 계획법 2

 

www.acmicpc.net/problem/11066

11066번: 파일 합치기

 

문제 풀이

 

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		StringBuilder sb = new StringBuilder();
        
		int t = sc.nextInt(), n, s[], dp[][], i, j, k, d;

		while( t-- > 0 ) {

			n = sc.nextInt();
			s = new int[n+1];			// file size sum
			for( i = 1; i <= n; i++ )
				s[i] = s[i-1] + sc.nextInt();

			dp = new int[n+1][n+1];
			for( d = 0; d < n; d++ ) {	// diagonal
				for( i = 1; i < n-d; i++ ) {
					j = i + d + 1;
					dp[i][j] = Integer.MAX_VALUE;
					for( k = i; k < j; k++ )
						dp[i][j] = Math.min( dp[i][j], dp[i][k] + dp[k+1][j] );
					dp[i][j] += s[j] - s[i-1];
				}
			}

			sb.append( dp[1][n] + "\n" );
		}
		sc.close();

		System.out.println( sb.toString() );
        
	}
}

 

- 구글링으로 푼 문제. 어렵다..

- 주의할 점 :
문제에서 "두 개의 파일을 합쳐서 하나의 임시파일을 만들고, 이 임시파일이나 원래의 파일을 계속 두 개씩 합쳐서 소설의 여러 장들이 연속이 되도록 파일을 합쳐나가고, 최종적으로는 하나의 파일로 합친다."
즉, 무조건 크기가 작은 두 파일씩 합치는 게 아니라는 뜻이다.

- 연쇄 행렬 곱셈 알고리즘과 비슷  ( hyunjiishailey.tistory.com/274 )