[Algorithm] 백준 11066 - 파일 합치기 풀이

풀이

처음문제를 읽고 허프만 코드를 만드는것 처럼 priority queue를 이용해 구현하였다. 하지만 제대로 된 답이 나오지 않았고 찾아보니 소설의 chapter를 인접한 페이지끼리만 합치는것이었다.

그 후 문제를 이해하고 DP라는 것 까지 알았지만 코드를 짜는것이 쉽지않다.

 

dp[i][j]  = i번째 장부터 j번째 장까지 합치는데 드는 최소한의 비용.

 

dp[i][j] = min{dp[i][k] + dp[k+1][j]} + sum[end] - sum[start-1]. 단, (start <= mid <  end )

(sum[end] - sum[start-1] 는 novel 의 start부터 end까지의 부분합)

 

여기서 sum[end] - sum[start-1]를 하는 것이냐 하면 다음의 예시와 같다.

40 30 30 50 파일 크기가 있을 때, 40 +30으로 Y1 파일을 만들고 30 + 50으로 Y2 파일을 만든다. Y1과 Y2를 합칠때의 비용 150이 들기 때문에 sum을 더해주는 것이다. 

 

1번째 for문은 최소값을 찾아주는 범위이다. 

예를들어 40 30 30 50의 input은 배열의 인덱스값이 1부터 4까지가 있다. 만약 gap이 1이라면 (40 30), (30 30), (30 50)으로 탐색하며 최소값을 찾는것이고 gap이 2라면 (40, 30, 30), (30, 30, 50)으로 탐색하며 최소값을 찾는것이다. 

 

 

dp[start][end]를 MAX로 초기화해주는 것도 중요하다. 최소값을 찾기위해 INT_MAX로 초기화해주어야 한다.

---

코드

#include <stdio.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <cstring>
#include <limits.h>
#define INF 999999

using namespace std;

int dp[510][510];

int main()
{
    int t;
    scanf("%d", &t);
    
    while(t--)
    {
        int k;
        scanf("%d", &k);
        vector<int> novel, sum;
        novel.clear();
        sum.clear();

        novel.resize(k + 1);
        sum.resize(k + 1);
        
        for(int i = 1; i <= k; i++)
        {
            scanf("%d", &novel[i]);
            sum[i] = sum[i - 1] + novel[i];
        }
        
        for(int gap = 1; gap < k ; gap++)
        {
            for(int start = 1; start + gap <= k ; start++)
            {
                int end = start + gap;
                dp[start][end] = INT_MAX;
                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]);
                }
            }
        }
        printf("%d\n", dp[1][k]);
        memset(dp, 0, sizeof(dp));
        
    }
    
}