[C++/백준] 11066 파일 합치기

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

11066번: 파일 합치기

[문제요약]

40 30 30 50이 있을 때, 괄호를 어떻게 잘 쳐주냐의 문제다. 

 

(((40+30)+30)+50) 쳐준다 할 때, 괄호 안에서 더해지고 나오는 값을 계속 기록했을 떄 최소가 되는 경우가 뭐냐

 

 

[문제 풀이]

 

처음 방식을 생각할 때 두 가지가 생각났다.

1) 완전 탐색 2) DP 

 

사실, 완전 탐색으로 풀 수 있는 문제는 아니기 때문에 바로 버리고, DP 아니면 다른 방법 있는지 찾아봤으나... 

=> 다른 방법 없음

=> 무조건 DP

 

사용한 방법은 인덱스를 기준으로 dp 처리를 해주는 것

idx	0	1	2	3
value	40	30	30	50

 

1) Sum[501][501]  => 구간합 

 

Sum[idx1][idx2] : idx1 ~ idx2 까지의 숫자 합

     ex) [0][2] : 40 + 30 + 30

           [2[[3] : 30 + 50

 

2) DP[501][501]

a. 길이가 1 인 경우     

     ex) DP[0][0] -> 더하기를 하지 않은  = 0

           DP[1][1]  = 0

           DP[N][N] = 0...

 

b. 길이가 2인 경우

     ex) DP[0][1] = Sum[0][0] + Sum[1][1]         => Sum[0][1] + DP[0][0] + DP[1][1]

           DP[i][i+1] = Sum[i][i] + Sum[i+1][i+1

 

c. 길이가 2 초과 ( 둘 중 최소 )

      ex) DP[0][2] = DP[0][0] + DP[1][2]

                             DP[0][1] + DP[2][2]                                             + Sum[0][2]

 

idx	0	1	2	3
0	0	70	100 + min(70, 60)
1		0	60	110 + min(60, 80)
2			0	80
3				0

 

[풀이]

#include<iostream>
#include<algorithm>
#include<vector>

using namespace std;

int T;
int sum[501][501];
int DP[501][501];

int main() {
	cin >> T;
	for (int t = 0; t < T; t++) {
		int N;
		cin >> N;
		fill(&DP[0][0], &DP[0][0] + 501 * 501, 2e9);
		fill(&sum[0][0], &sum[0][0] + 501 * 501, 0);
		for (int i = 0; i < N; i++) {
			cin >> DP[i][i];
			DP[i][i] = 0;
		}

		// 합을 구해주는 부분. 
		for (int s = 0; s < N-1; s++) {
			for (int e = s + 1; e < N ;e++) {
				for (int i = s; i <= e;i++)
					sum[s][e] += sum[i][i];
			}
		}

		// l : idx1 ~ idx2 까지의 길이
		// s : 시작 idx1
		// m : s ~ s+l (idx1 ~ idx2) 중간 지점을 두고 돌아가면서 최소를 구한다. 
		for (int l = 1; l < N; l++) {
			for (int s = 0; s < N - l; s++) {
				for (int m = 0; m < l; m++) {
					DP[s][s + l] = min(DP[s][s + l], DP[s][s + m] + DP[s + m + 1][s + l]+sum[s][s+l]);
				}
			}
		}


		cout << DP[0][N - 1] << '\n';
		
	}
}