11066 파일 합치기

백준 11066번 파일 합치기 : https://www.acmicpc.net/problem/11066

11066번: 파일 합치기

 

[풀이 전]

예를 들어, 40 30 30 50의 입력을 받으면

1 : 40 / 30 /  30 /  50

2 : 40 30 / 30 30 / 30 50

3 : 40 30 30 / 30 30 50

4 : 40 30 30 50

와 같은 순서로 1부터 4까지 파일 묶음의 최소 비용을 순서대로 구해가면 될 것이라 생각했다. ( ex. 3 : 40 30 30의 최소비용 구하기)  

 

최소 비용은 어떤 식으로 구할 것인가? 만약 파일 4개를 묶는다면 '1+3', '2+2', '3+1'의 경우가 있다.

즉, 저 세개의 경우 중 최소비용을 저장하면 된다. 

 

① 1부터 N까지 합쳐지는 파일의 개수를 확장하며 각 경우의 최소바용을 구해간다.

② 파일의 개수가 i일 때, 

i = 1+(i-1), 2+(i-2), 3+(i-3)... 으로 나누어 각각의 값을 계산해 최소비용을 구해 저장한다.  

 

 

[문제 풀이]

#include <iostream>
#include <climits>
using namespace std;
#define NMAX 501

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int T;
	cin >> T;
	for (int i = 0; i < T; i++) {
		int dp[NMAX][NMAX] = {};
		int N, K;
		cin >> N;
		for (int i = 1; i <= N; i++) {
			cin >> K;
			dp[1][i] = K;
		}

		for (int i = 2; i <= N; i++) { // 파일의 개수
			for (int k = 1; k <= N - i + 1; k++) { 
				int kmin = 0;
				for (int j = 1; j <= i - 1; j++) { // 이전까지 파일을 합치는데 들었던 비용
					int temp = 0;
					if (j > 1)temp += dp[j][k];
					if (i - j > 1) temp += dp[i - j][k + j];

					if (kmin == 0 || temp < kmin) kmin = temp;
				}
				dp[i][k] = kmin;

				for (int l = k; l < k + i; l++) { // 현재 파일 합치는 비용
					dp[i][k] += dp[1][l];
				}
			}
		}
		cout << dp[N][1] << "\n";
	}

	return 0;
}

 

dp[NMAX][NMAX]	각 경우에 따른 최소비용을 저장하는 배열
int i	합쳐진 파일의 개수
int k	파일은 총 'N-i+1'만큼의 묶음으로 나누어짐.  몇번째 묶음의 최소비용을 구하는지 가리키기 위한 변수
for (int j = 1; j <= i - 1; j++) {}	j를 1부터 i-1까지 증가시키면서, 현재 k가 가리키고 있는 파일 묶음의 합쳐질 수 있는 경우의 수를 고려. 다양한 경우의 비용을 계산 및 비교해 최소비용 kmin에 저장
for (int l = k; l < k + i; l++) {}	dp에는 여태까지 사용된 비용을 저장하므로, 현재 파일을 합치는데 드는 비용을 따로 계산하여 더함

[comment]

dp문제는 규칙을 찾는 문제 같아서 개인적으로는 재밌는 것 같다. 다만 시간 복잡도가 N^3인 점이 찝찝해서 찾아보니 N^2으로 푸는 방법도 존재한다고 하여 공부해봐야할 것 같다.