백준 - 파일 합치기(11066)

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

11066번: 파일 합치기

 

 

어려운 DP문제였다.

 

50 40 30

의 cost를 계산한다고 하면

(50 + 40) + (50 + 40 + 30) = 210

(40 + 30) + (50 + 40 + 30) = 190

 

해당 예시를 보면

꼭 전체합을 한번 더 더하는 모습을 볼 수 있다.

 

예시를 보면

40 30 30 50

 a   b   c   d

 

각 알파벳을 지정해 주며

a + b + c 라흐만  40, 30, 30을 합쳐을 때의 cost라고 생각해 본다.

 

 

 

 

DP 초기 테이블이다.

	a	b	c	d
a	0	INF	INF	INF
b	INF	0	INF	INF
c	INF	INF	0	INF
d	INF	INF	INF	0

 

 

탐색을 대각선 방향으로 진행해 준다.

 

 

	a	b	c	d
a	a	a+b	a+b+c	a+b+c+d
b	INF	b	b+c	b+c+d
c	INF	INF	c	c+d
d	INF	INF	INF	d

해당 테이블 안 각각 cost값이 들어가는 위치이다.

참고용이다.

 

 

빨간색 동그라미 두 개 더하고 + (40+30) = 70

dp[a][a] + dp[b][b] + (a+b)

 

동그라미 + (30 + 30) = 60

dp[b][b] + dp[c][c] + (b + c)

 

 

 

동그라미 + (30 + 50) = 80

dp[c][c] + dp[d][d] + (c+d)

 

 

 

 

그다음 dp[a][c]를 탐색

dp[a][a] + dp[b][c] + (40 + 30 + 30)

dp[a][b] + dp[c][c] + (40 + 30 + 30)

둘 중에 최솟값

 

 

 

 

dp[b][b] + dp[c][d] + (30 + 30 + 50)

dp[b][c] + dp[d][d] + (30 + 30 + 50)

둘 중에 최솟값

 

 

 

마지막

dp[a][a] + dp[b][d] + (40 + 30 + 30 + 50) = 170 + 150

dp[a][b] + dp[c][d] + (40 + 30 + 30 + 50) = 150 + 150

do[a][c] + dp[d][d] + (40 + 30 + 30 + 50) = 160 + 150

 

300이 나온다.

 

 

#include <iostream>
#include <vector>
#include <numeric>
using namespace std;
int main() {
	
	int stage;
	cin >> stage;
	for (int s = 0; s < stage; s++) {
		int	count;
		cin >> count;
		vector<vector<long long>>	dp(count, vector<long long>(count, 100000000000));
		vector<int> data;
		vector<int> section_sum(count, 0);
		for (int i = 0; i < count; i++) {
			int temp;
			cin >> temp;
			data.push_back(temp);
			dp[i][i] = 0;
		}
		section_sum[0] = data[0];
		for (int i = 1; i < count; i++) {
			section_sum[i] = section_sum[i - 1] + data[i];
		}

		for (int i = (count - 1); i >= 1; i--) {
			for (int j = 0; j < i; j++) {
				int section_data = accumulate(data.begin() + j, data.begin() + count - i + j + 1, 0);
				for (int k = j; k < count - i + j; k++) {
					dp[j][count - i + j] = min(dp[j][count - i + j], dp[j][k] + dp[k + 1][count - i + j] + section_data);
				}
			}
		}
		cout << dp[0][count - 1] << endl;
	}
}