파일 합치기 - 11066

//11066 - 파일 합치기
 
#include <iostream>
using namespace std;
 
#define INF 100000000
 
int N;
int arr[500];
int sub[500];
int dp[500][500];
//Kruth's optimization를 위한 배열
int num[500][500];
 
void init()
{
    cin >> N;
    for(int i = 0; i<N; ++i)
        for(int j = 0; j<N; ++j)
            dp[i][j] = INF;
    for(int i = 0; i<N; ++i)
        cin >> arr[i];
    sub[0] = arr[0];
    for(int i = 1; i<N; ++i)
        sub[i] = sub[i-1] + arr[i];
    for(int i = 0; i<N; ++i)
    {
        dp[i][i] = 0;
        num[i][i] = i;
    }
}
 
int merge(int x, int y)
{
    if(x == 0) return sub[y];
    return sub[y] - sub[x-1];
}
 
int main()
{
    int C; cin >> C;
    while(C--)
    {
        init();
        for(int d = 1; d < N; ++d)
            for(int i = 0; i + d<N; ++i)
            {
                int j = i + d;
                for(int k = num[i][j-1]; k<=num[i+1][j]; ++k)
                {
                    int v = dp[i][k] + dp[k+1][j] + merge(i, j);
                    if(dp[i][j] > v)
                        dp[i][j] = v, num[i][j] = k;
                }
            }
        cout << dp[0][N-1] << "\n";
    }
}

 

 

 

 

 

 

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

11066번: 파일 합치기

 

 

 

 

 

 

파일 합치기

DP문제 중 kruth's optimization을 적용할 수 있는 문제입니다.

https://onedaycoding.tistory.com/82

Kruth's optimization

C(s, d) : s~d구간을 구하는 것중 최소비용

D(s, d) : s~d구간의 원소들의 합

C(s, d) = min(s < k < d){C(s, k) + C(k+1, d)} + D(s, d)