백준11066 파일 합치기

작성일 | In

문제 링크

  • http://icpc.me/11066

문제 출처

  • 2015 ACM-ICPC 대전 인터넷 예선 F번

사용 알고리즘

  • DP

시간복잡도

  • O(n3)

풀이

n이 최대 500이기 때문에 O(n3)정도에 해결하면 됩니다.

dp[i][j]를 i번째 파일부터 j번째 파일까지 합칠 때 드는 최소 비용이라고 정의합시다.
s[i]는 첫 번째 파일부터 i번째 파일까지 모든 파일 크기의 합이라고 정의합시다. (prefix sum)
i부터 j까지의 파일을 합치는 것은 i부터 k까지 합치고, k+1부터 j까지 합치는 것과 같습니다. (단, i ≤ k < j)
점화식을 세워봅시다.
dp[i][j] = min(dp[i][k] + dp[k+1][j]) + s[j] - s[i-1]

3중 for문은 이용해 dp배열을 채워주면 됩니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <bits/stdc++.h>
using namespace std;

int dp[510][510], k[510][510];

void solve(int n){
	vector<int> v(n+1), s(n+1);
	for(int i=1; i<=n; i++) cin >> v[i], s[i] = s[i-1] + v[i];
	for(int m=1; m<n; m++){
		for(int i=1; m+i<=n; i++){
			int j = i+m; dp[i][j] = 1e9+7;
			for(int k=i; k<j; k++){
				dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j] + s[j] - s[i-1]);
			}
		}
	}
	cout << dp[1][n] << "\n";
}

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	int t; cin >> t;
	while(t--){
		int n; cin >> n;
		solve(n);
	}
}