백준 11066 파일 합치기

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

11066번: 파일 합치기

 

 

 

EXPLANATION

 

소설의 여러 장들이 연속이 되도록(서로 인접한 파일들만 합칠 수 있음) 파일을 합쳐나가고, 최종적으로는 하나의 파일로 합친다.

두 개의 파일을 합칠 때 필요한 비용(시간 등)이 두 파일 크기의 합이라고 가정할 때, 최종적인 한 개의 파일을 완성하는데 필요한 비용의 총 합을 계산하시오.

 

 

(파일을 합치는 데 드는 비용)  = (합쳐지는 파일의 모든 크기의 합)

 

(현재 두 파일을 합치는 데 드는 총 비용) 

= (각 두 파일을 만드는 데 들었던 각 총 비용의 합) + (파일을 합치는 데 드는 비용)

=  (각 두 파일을 만드는 데 들었던 각 총 비용의 합) + (합쳐지는 파일의 모든 크기의 합)

총 = 누적

 

ex)

 C1, C2, C3, C4가 연속적인 네 개의 장을 수록하고 있는 파일이고,

파일 크기가 각각 40, 30, 30, 50 이라고 하자.

예를 들어서, C2와 C3을 합치고 이후 거기에 C1을 합치고 최종적으로 거기에 C4를 합치자고 하자.

 

먼저 C2와 C3를 합쳐서 임시파일 X1을 만든다. 이때 비용 60(= 30 + 30)이 필요하다.

60 = (0+0) + (60)

현재 파일을 합치는 데 드는 총 비용: 60

 

그 다음으로 C1과 X1을 합쳐 임시파일 X2를 만들면 비용 100(= 40 + 30 + 30)이 필요하다.

160 = (0 + 60) + (100)

현재 파일을 합치는 데 드는 총 비용: 160

 

최종적으로 X2와 C4를 합쳐 최종파일을 만들면 비용 150(= 40 + 30 + 30 + 50)이 필요하다. 

310 = (160 + 0) + (150)

현재 파일을 합치는 데 드는 총 비용: 310

따라서, 최종의 한 파일을 만드는데 필요한 비용의 합은 310(= 60+100+150)이다. 

 

 

합치는 범위가 2인거부터 오름차순으로 dp에 넣어야 더 큰 범위를 나타내는 dp에 값을 할당할 때, 이전의 더 작은 범위의 dp값을 이용할 수 있다. (합치는 범위가 1이면 안합치거므로 비용 0)

합치는 범위가 정해졌으면, 범위의 시작을 정하고, 이후, 그 범위를 두 부분으로 나누는 기준을 정한다.

이에 대한 정보를 index로 가지는 dp에 이에 대한 합치는 총 비용을 할당한다.

for (int i = 1; i <= K; i++)
{
    for (int j = 1; j <= K - i; j++)
    {
        dp[j][i + j] = INF;
        for (int k = j; k < i + j; k++)
        {
            dp[j][i + j] = min(dp[j][i + j], dp[j][k] + dp[k + 1][i + j] + sum[i + j] - sum[j - 1]);
        }
    }
}

 

 

CODE

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
#define INF 1000000000    //1000000000 > (500*(501)/2 -1)*1000

int T, K;
int sum[501], file[501], dp[501][501];

int main()
{
	cin >> T;

	while (T--)
	{
		cin >> K;
		for (int i = 1; i <= K; i++)
		{
			cin >> file[i];
			sum[i] = sum[i - 1] + file[i];
		}

		for (int i = 1; i <= K; i++)    //base dp[j][j + 0] = 0;
		{
			for (int j = 1; j <= K - i; j++)    //base sum[0] = 0;
			{
				dp[j][i + j] = INF;
				for (int k = j; k < i + j; k++)
				{
					dp[j][i + j] = min(dp[j][i + j], dp[j][k] + dp[k + 1][i + j] + sum[i + j] - sum[j - 1]);
				}
			}
		}

		cout << dp[1][K] << "\n";

	}

}