[11066번] 파일 합치기

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

1. Dynamic Programming

2. 점화식 세우는 방법

3중 포문을 이용하여 문제를 해결 할 수 있다.

점화식은 다음과 같다.

dp[j][i] :: j~i번째까지 파일을 합칠 때 최소비용

3중포문은 다음과 같이 이용한다.

for (int i = 2; i <= n; i++)

{

for (int j = i - 1; j > 0; j--)

{

dp[j][i] = 987654321;

for (int k = j; k <= i; k++)

dp[j][i] = min(dp[j][i], dp[j][k] + dp[k + 1][i]);

dp[j][i] += pSum[i] - pSum[j - 1];

}

}

위의 코드가 위의 그림과 같은 역할을 하게 된다.

dp[j][i]의 최소비용을 찾기 위해서는 그 사이에 있는 모든 dp[j][k]와 dp[k+1][i] 사이의 최소를 찾으면 된다.

소스 코드 : 

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <memory.h>
 
using namespace std;
 
int dp[502][502];
int arr[502];
int pSum[502];
 
int main()
{
    int tc;
    scanf("%d", &tc);
 
    while (tc--)
    {
        memset(dp, 0, sizeof(dp));
        memset(arr, 0, sizeof(arr));
 
        int n;
        scanf("%d", &n);
 
        for (int i = 1; i <= n; i++)
        {
            scanf("%d", &arr[i]);
            pSum[i] = pSum[i - 1] + arr[i];
        }
 
        for (int i = 2; i <= n; i++)
        {
            for (int j = i - 1; j > 0; j--)
            {
                dp[j][i] = 987654321;
                for (int k = j; k <= i; k++)
                    dp[j][i] = min(dp[j][i], dp[j][k] + dp[k + 1][i]);
 
                dp[j][i] += pSum[i] - pSum[j - 1];
            }
        }
        printf("%d\n", dp[1][n]);
 
    }
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>