백준_파일 합치기_11066[Java]

문제

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

11066번: 파일 합치기

 

풀이

DP로 해결한다. 

생각하기 쉽지 않아 다른 분들 코드를 참고했다.

 

점화식은 다음과 같다. 

DP[j][i]  =  DP[j][s] + DP[s+1][i] + SUM[j~i]

* DP[j][i] : j에서 i까지의 파일을 합치는데 드는 최소 비용

* SUM[j~i]는  j ~ i 까지의 총합으로 SUM[i] - SUM[j-1] 이다.

 

/*

* 각 장은 다른 파일에 저장

* 이 다른 파일을 최종 합쳐서 완성본인 파일 하나 만듦

* 과정 : 두개의 파일을 합친다 -> 임시파일 

* 이 임시파일이나 원래의 파일 두개 합쳐서 여러 장들이 연속되도록 합쳐나간다. 

* 합치는 비용 : 두 파일 크기의 합 

* 필요한 비용의 최소 합을 구하자 

*/

 

코드

 

import java.util.Scanner;

public class Main {
	static int T, K;
	static int[] fic;
	static int[] sum;
	static int[][] dp;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		T = sc.nextInt();

		for(int test = 0; test < T; test++) {
			
			K = sc.nextInt();
			
			fic = new int[K+1];
			sum = new int[K+1];
			dp = new int[502][502];
			
			for(int i = 1; i <= K; i++) {
				fic[i] = sc.nextInt();
				sum[i] = sum[i-1]+ fic[i];
			}
			
			for (int i = 2; i <= K; i++)
	        {
	            for (int j = i - 1; j > 0; j--)
	            {
	                dp[j][i] = 999999999;
	                for (int s = j; s <= i; s++)
	                    dp[j][i] = Math.min(dp[j][i], dp[j][s] + dp[s + 1][i]);
	 
	                dp[j][i] += sum[i] - sum[j - 1];
	            }
	        }

			
			System.out.println(dp[1][K]);
			
			
		}
		
		sc.close();
	}

}

 

참고

https://stack07142.tistory.com/69

BOJ#11066 파일 합치기 (Merging Files)

https://www.crocus.co.kr/1073

[11066번] 파일 합치기

https://xyom.github.io/2017/12/26/%EB%B0%B1%EC%A4%80%2011066%20%ED%8C%8C%EC%9D%BC%ED%95%A9%EC%B9%98%EA%B8%B0/

백준 11066 파일합치기