186. 11066(파일 합치기) - 자바

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

class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		int T = Integer.parseInt(br.readLine());

		for (int m = 0; m < T; m++) {
			int K = Integer.parseInt(br.readLine());
			int[] page = new int[K + 1];

			String[] tmp = br.readLine().split(" ");
			for (int x = 1; x <= tmp.length; x++) {
				page[x] = Integer.parseInt(tmp[x - 1]);
			}

			// 누적합
			int[] sumPage = new int[K + 1];
			for (int x = 1; x <= K; x++) {
				sumPage[x] = sumPage[x - 1] + page[x];
			}

			// 동적 계획법
			int[][] DP = new int[K + 1][K + 1];
			for (int i = 2; i < K + 1; i++) {
				for (int j = 1; j < K + 2 - i; j++) {
					// 최소값 비교를 위해 사용함.
					DP[j][j + i - 1] = Integer.MAX_VALUE;
					for (int k = 0; k < i - 1; k++) {
						DP[j][j + i - 1] = Math.min(DP[j][j + i - 1],
								DP[j][j + k] + DP[j + k + 1][j + i - 1] + (sumPage[j + i - 1] - sumPage[j - 1]));
					}
				}
			}
			sb.append(DP[1][K]).append("\n");
		}
		System.out.print(sb);
	}
}

문제요약

모든 페이지를 합하는데 드는 최소 비용을 구하라

 

설명

DP의 가장 어려운 유형의 문제

이 문제의 기본적인 idea만 알아도 다른 문제에 많이 활용할 수 있다고 한다.

 

입력이 아래와 같을 때,

 

4

40 30 30 50

 

먼저 누적합을 구해주면 아래 list와 같다.

[0, 40, 70, 100, 150]

누적합을 구해주는 이유는 두 개의 파일을 합칠 때 필요한 비용(두 파일 크기의 합)을 

편하게 연산하기 위함이다.

 

이 문제는 DP를 정의하는게 정말 어렵다.

먼저 DP는 2차원 배열을 사용할 것이고,

DP[i][j]는 i에서 j까지 합하는데 필요한 최소 비용이 된다.

 

파일 한 개(파일의 길이 : 1)는 비용이 들지 않으므로 비용이 0이고, 

파일의 길이가 2일 경우부터 4일 경우까지 비용을 확인해보아야 한다.

예를 들어 파일의 길이가 3일 경우는 파일을 합치는 방법을 

(1번) + (2번,3번)인 경우와 (1번, 2번) + (3번)인 경우로 나눌 수 있다.

이렇게 나눠보기 위해 기존의 두 파일을 합치는 비용이 미리 계산되어 있어야 한다.

누적합 S = [0, 40, 70, 100, 150]

 

 

길이가 2일 경우,

(1,2), (2,3), (3,4) 파일로 나눌 수 있는데,

1번부터 2번파일까지의 비용은 (1~1의 비용(0) + 2~2의 비용(0)) + (1~2까지 누적합(70)) = 70 이 되고,

2번부터 3번파일까지의 비용은 (2~2의 비용(0) + 3~3의 비용(0)) + (2~3까지 누적합(60)) = 60 이 되고,

3번부터 4번파일까지의 비용은 (3~3의 비용(0) + 4~4의 비용(0)) + (2~3까지 누적합(80)) = 80 이 된다.

여기서 DP[][]의 상태는 아래 그림과 같다.

 

 

다음 길이가 3일 경우,

(1 + 2,3), (1,2 + 3), (2, + 3,4), (2,3 + 4) 파일로 나눌 수 있는데

1번부터 3번파일까지의 비용은 min(1~1의 비용(0) + 2~3의 비용(60).

 1~2의 비용(70) + 3~3의 비용(0)) 

+ (1~3까지의 누적합(100)) = 160 이 된다.

2번부터 4번파일까지의 비용은 min(2~2의 비용(0) + 3~4의 비용(80).

 2~3의 비용(60) + 4~4의 비용(0)) 

+ (2~4까지의 누적합(110)) = 170 이 된다.

 

 

마지막으로 길이가 4일 경우,

(1 +,2,3,4), (1,2 + 3,4), (1,2,3 + 4) 파일로 나눌 수 있는데,

1번부터 4번파일까지의 비용은 min(1~1의 비용(0) + 2~4의 비용(170).

 1~2의 비용(70) + 3~4의 비용(80),

 1~3의 비용(160) + 4~4의 비용(0))

 + (1~4까지의 누적합(150)) = 300 이 된다.

 

여기서 마지막으로 1~4번까지의 파일을 합쳐야 하므로

DP[1][N]을 출력해주면 된다.

 

여기서 찾을 수 있는 점화식은

DP[i][k] + DP[k+1][j] + sum(A[i]~A[j]) 가 될 것이다.

(i~k)까지 비용의 합과 그 다음 (k+1지점부터 마지막 지점)까지의 합의 최소에

(i~j)까지의 누적합을 더해주면 얻고자하는 해를 얻을 수 있다.

 

여기서 DP[][]는 i부터 j까지 파일을 합치는데 드는 비용으로 정의하고 푸는 것이 중요한 포인트인것 같다.

 

 

출처: https://data-make.tistory.com/402 [Data Makes Our Future:티스토리]