[백준 11066] 파일 합치기

문제 링크 => 11066번: 파일 합치기 (acmicpc.net)

11066번: 파일 합치기

 

다이나믹 프로그래밍 문제이다.

 

이 문제는 알고리즘 시간때 배웠던 행렬 곱 연산을 최소로 만드는 그 문제와 비슷해서 한번에 풀렸다.

 

T(i, j) =  파일 i 번째에서 j 번째까지를 하나의 파일로 합칠 때 최소 시간

S(i, j) =  파일 i 번째에서 j 번째까지를 합치는 과정에서 걸리는 최소 시간

 

예를 들어서 20, 50, 30 이 있다고 하자.

 

S(1, 1) = 20, S(2, 2) = 50, S(3, 3) = 30 이고

T(1, 1) = T(2, 2) = T(3, 3) = 0 임을 알 수 있다.

 

S(1, 2) = 20 + 50 = 70, S(2, 3) = 50 + 30 = 80 이고

T(1, 2) = T(1, 1) + T(2, 2) + S(1, 2) = 70, T(2, 3) = T(2, 2) + T(3, 3) + S(2, 3) = 80 임을 알 수 있다.

 

S(1, 3) = S(1, 1) + S(2, 3) = 20 + 80 = 100 이거나             

S(1, 3) = S(1, 2) + S(3, 3) = 70 + 30 = 100 이다.

 

이 경우에는 같지만 i, j의 격차가 커질 수록 달라질 수 있으므로 minimum 값을 잡아줘야 한다.

 

T(1, 3) = T(1, 1) + T(2, 3) + S(1, 3) = 80 + 100 = 180 이거나             

T(1, 3) = T(1, 2) + T(3, 3) + S(1, 3) = 70 + 100 = 170 이다.

 

이 경우에는 170이 더 작으므로 T(1, 3) = 170 즉, 하나의 파일로 합칠 때 최소 시간은 170 이다.

 

위와 같이 노가다를 함으로써 얻어낸 Optimal Substructure는 다음과 같다.

 

 

 

S(i, j) = min(S(i, j), S(i, k) + S(k + 1, j)) (i <= k <= j - 1)

T(i, j) = min(T(i, j), T(i, k) + T(k + 1, j) + S(i, j)) (i <= k <= j - 1)

 

 

 

 

Solution Code

 

 

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <math.h>
#include <string>
#include <stdlib.h>

#define INF 100000000

using namespace std;

int solution(int* f, int n) 
{
	int** T, ** S;
	int result;
	
	T = (int**)malloc(sizeof(int*) * (n + 1));
	S = (int**)malloc(sizeof(int*) * (n + 1));
	for (int i = 0; i <= n; i++) {
		T[i] = (int*)malloc(sizeof(int) * (n + 1));
		S[i] = (int*)malloc(sizeof(int) * (n + 1));
	}

	for (int i = 1; i <= n; i++)
		S[i][i] = f[i], T[i][i] = 0;
	for (int gap = 1; gap < n; gap++) {
		for (int i = 1; i <= n - gap; i++) {
			int j = i + gap;
			S[i][j] = T[i][j] = INF;
			for (int k = i; k < j; k++) {
				S[i][j] = min(S[i][j], S[i][k] + S[k + 1][j]);
				T[i][j] = min(T[i][j], T[i][k] + T[k + 1][j] + S[i][j]);
			}
		}
	}
	result = T[1][n];
	
	for (int i = 0; i <= n; i++) {
		free(S[i]);
		free(T[i]);
	}
	free(S);
	free(T);

	return result;
}

void test() 
{
	int n;
	int* f;
	
	cin >> n;
	f = (int*)malloc(sizeof(int) * (n + 1));
	for (int i = 1; i <= n; i++)
		cin >> f[i];
	cout << solution(f, n) << endl;
}

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

	int t;
	cin >> t;
	while (t--)
		test();

	return 0;
}