백준[11066] 파일 합치기

 

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

 

이 문제를 봤을 때 Priorty Queue로 풀 수 있을 줄 알았다. 하지만 제약 조건에서 "연속이 되도록 파일을 합쳐나가고, ..."라는 인접 제약조건이 있기 때문에 인접 조건을 무시하는 Priorty Queue로 풀 수 없었다.

 

DP문제라는 사실을 알아도 풀지 못해 정답을 찾아봐도 처음엔 이해하기 어려웠다...

 

풀이

DP[i][j]를 파일 i번부터 j번까지 합쳤을때 최소비용 이라고 정의하자. 이러면 DP[1][N]이 정답이다.

그리고 SUM[i][j]는 파일 i번부터 j번까지 파일을 합친 크기라 정의하자.

 

그러면 다음과 같은 수식을 구할 수 있다.

DP[i][j] = min(DP[i][m] + DP[m+1][j] + SUM[i][m] + SUM[m+1][j]) ... (i <= m < j, DP[k][k] = 0)

이 때 SUM[i][m] + sum[m+1][j] = sum[i][j]로 줄일 수 있다.

 

다시 식을 정리하면 

DP[i][j] = min(DP[i][m] + DP[m+1][j]) + SUM[i][j]이다.

 

그리고 DP[i][j]를 찾으려면 DP[i][m], DP[m+1][j]의 값이 계산되어있어야한다.

즉, i와 j의 차이가 작은 것 부터 큰 것으로 확장하며 연산해야한다.

 

개인적으론 이 확장하면서 연산을 이해하는 코드가 좀 어려웠다.

 

정답 코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>
#define INF 987654321

using namespace std;

int T, n;
vector<int> v;
vector<vector<int>> dp;
int ans;


int main()
{
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	cin >> T;
	while(T-->0) {
		cin >> n;
		v = vector<int>(n+1);
		dp = vector<vector<int>>(n+1, vector<int>(n+1));
		ans = 0;
		for(int i = 1; i <= n; i++) {
			int x; cin >> x;
			v[i] = v[i-1] + x;
		}
		for(int k = 1; k < n; k++) { // k = j - i = gap
			int i = 1;
			int j = k + 1;
			for(int u = 0; u < n-k; u++) { // j가 n일때까지 반복
				dp[i][j] = INF;
				for(int m = i; m <= j - 1; m++) { // i <= m < j 에서의 dp[i][j]값 구하기
					dp[i][j] = min(dp[i][j], dp[i][m] + dp[m+1][j] + v[j] - v[i-1]);
				}
				i++;
				j++;
			}
		}
		cout << dp[1][n] << '\n';
	}
	return 0;
}