백준 11066 파일합치기

파일합치기

최근에 팰린드롬? 문제를 재미있게 풀고, 파일 합치기 를 풀었다.

동적 계획법은 언제나 어렵고 알고나면 아! 느낌이 든다.

위 두 문제를 풀면서 배운점은 원랜 꼭 이전의 어떤 값을 이용해서 다음 값을 만들어야 하는 점화식의 형태를 생각했었는데 그게 아니고 d[i][j]= i부터 j까지의 어떤 값 처럼 좀더 유동적이게 생각해야 하는 것이다. 다차원 dp가 그런 점이 특히 강한 것 같다.

문제분석

파일의 챕터가 주어지면, 챕터를 더한 값이 비용이 되고, 최소비용을 구하는 문제이다.

예시를 드는게 더 쉽다.

예를들어 40 30 30 50이면 2,3을 합쳐서 파일 x1(비용60)이 나오고, 1,x1을 합쳐서 파일 x2(비용100)가 나온다. 최종적으로 x2와 4를 합쳐서 y(비용150)이 나온다.

여기서 나오는 비용을 모두 더하면 60+100+150 = 310인데,

1,2 를 합치고(x1) 3,4 합치고(x2) x1,x2합치면 70+80+150=300이 나온다.

1. 파일 1,2,3,4를 놓고 보면 합치는 방법을 생각해본다.
   • (1,234) (12,34) (123,4) 세가지 방법이 있다.
2. 첫번째의 (1,234)는 또 다음과 같은 방법으로 나뉜다
   • (1,(2,34)(23,4)) -> 즉 재귀적으로 구현 가능하다.
3. 위와같이 풀면 시간초과가 난다. (O(N-1)!) dp의 꽃 memoization을 사용해야한다.
   • d[i][j]에 i부터 j까지 소설을 구성할 때 드는 최소 비용을 저장한다.

소스

#include <iostream>
#include <vector>
#include<cstring>
#include <algorithm>
using namespace std;
int chapter[501] = { 0 };
int d[501][501] = { 0 };
int go(int first,int last) {
	if (d[first][last] != -1)
		return d[first][last];
	
	if (first == last)
		return 0;
	int sum = 0;
	for (int i = first; i <= last; i++) {
		sum += chapter[i];
	}
	int ans=-1;
	for (int i = first; i <= last - 1; i++) {
		int tmp = go(first, i)+go(i+1, last)+sum;
		if (ans == -1 || ans > tmp)
		{
			ans = tmp;
		}
	}
	d[first][last] = ans;
	return ans;
}

int main() {
	int t;
	cin >> t;
	while (t--) {
		memset(d, -1, sizeof(d));
		int n;
		cin >> n;
		for (int i = 1; i <= n; i++)
			cin >> chapter[i];
		cout << go(1, n)<<'\n';
	}
}