[ICPC] 백준 11066 - 파일 합치기

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

 

다음 DP 테이블을 세운다.

 

dp[i][j] := i번째부터 j번째 파일까지 합치는 최소 비용

 

4중 반복문으로 i번째 책을 시작으로 j + 1개의 연속된 책을 합치려고 하는데 pivot이 m번째 책일 때 양 옆의 책들을 합치는 비용을 계산하면서 테이블을 채우는 방법을 생각할 수 있다.

 

다만 연속된 책을 합치는 과정을 반복문마다 수행하면 시간 초과를 받을 위험이 있다. 누적합으로 파일을 합치는 비용을 미리 계산하면 일부 연속된 책을 합치는 비용을 $O(1)$의 시간 복잡도로 처리할 수 있으므로 3중 반복문으로 줄어든다.

 

주어지는 TC에 대해 3중 반복문으로 테이블을 채운 후 최소 비용을 출력하면 정답을 받을 수 있다.

 

전체 코드

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int book[501][501];
int partialmin[501];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
   
    int n;
    cin >> n;
    while(n--)
    {
        int t;
        cin >> t;

        vector<int> cost(t + 1);
        for (int x = 1; x <= t; ++x)
        {
            cin >> cost[x];
            partialmin[x] = partialmin[x - 1] + cost[x];
        }
        
        for (int i = 1; i < t; ++i)
        {
            for (int j = 1; j + i <= t; ++j)
            {
                int liner = j + i;
                book[j][liner] = 1e9 + 7;
                
                for (int m = j; m < liner; ++m)
                {
                    book[j][liner] = min(
                        book[j][liner],
                        book[j][m] + book[m + 1][liner] + partialmin[liner] - partialmin[j - 1]
                    );
                }
            }
        }

        cout << book[1][t] << '\n';
    }
}