[Algorithm]Baekjoon 11066번 :: 파일 합치기

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

11066번: 파일 합치기

 
 
using namespace std;
 
int t, k, input;
int arr[501] = { 0 };
int sum[501] = { 0 };
int dp[501][501] = { 0 };
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> t;
 
    for (int i = 0; i < t; ++i)
    {
        cin >> k;
 
        memset(dp, 0, sizeof(dp));
 
        for (int j = 1; j <= k; ++j)
        {
            cin >> arr[j];
            sum[j] = sum[j - 1] + arr[j];
        }
 
        
        for (int gap = 1; gap < k; ++gap)
        {
            for (int start = 1; start + gap <= k; ++start)
            {
                int end = start + gap;
                dp[start][end] = 0x3f3f3f3f;
                
                for (int mid = start; mid <= end; ++mid)
                {
                    dp[start][end] = min(dp[start][end], dp[start][mid] + dp[mid + 1][end] + sum[end] - sum[start-1]);
                }
            }
        }
 
        cout << dp[1][k] << endl;
    }
}
 
 
 

 

이전의 행렬곱문제랑 거의 비슷하고, 사실상 코드가 다른것은 합치는 부분일 뿐이다.

합칠 때 mid를 기점으로 나눈 두 구간의 최솟값과 start~end의 누적값을 더해줘야 한다.

사실 그냥 코드로만 봤을 때는 이해가 잘 안갔는데, 직접 그려보면서 하니까 결국 다 더해줘야한다는것은 알게됐는데..

 

인덱스 1~4구간의 최소비용을 구한다 가정하자.

쪼개는 과정에서 1~2,  3~4가 되는 경우가 있다.

그러면 dp[1][2]와 dp[3][4]를 구해야 할 것이다.

dp[1][2]는 다시 dp[1][1]과 dp[2][2]로 쪼개진다.

dp[i][i]는 값이 당연히 0이다. 자기자신을 합칠일은 없으니까. 그러니 0 + 0 + arr[1] + arr[2], 즉 sum(1,2)를 더해준다.

 

이건 결과론적인 설명이긴 한데, 뭔가 더 어떻게 설명해야할지 잘 모르겠다..

sum(start,end)는 결국 dp[start,mid]의 파일과 dp[mid+1,end]의 파일을 합치는 '비용'이라 생각하면 된다.