백준 11066 파일 합치기(c++)

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

11066번: 파일 합치기

이 문제는 파일을 합치는데 최소 비용을 구하는 문제입니다. 테스트케이스를 예시로 들면, C1, C2, C3, C4의 파일 크기는 각각 40 30 30 50입니다. 파일을 합치는 경우의 수는 총 3가지입니다.

(C1), (C2, C3, C4)

(C1, C2), (C3, C4)

(C1, C2, C3), (C4)

1번 경우에는 C2 + C3 = 60, C2 + C3 + C4 = 60 + 50 = 110, C1 + C2 + C3 + C4 = 150, 총 320이 듭니다.

2번 경우에는 C1 + C2 = 70, C3 + C4 = 80, C1 + C2 + C3 + C4 = 150, 총 300이 듭니다.

3번 경우에는 C1 + C2 = 70, C1 + C2 + C3 = 100, C1 + C2 + C3 + C4 = 150, 총 320이 듭니다.  

 

이 중 최솟값은 300이기 때문에 300을 출력해줘야 합니다. 

 

<코드>

#include <iostream>
#include <cstring>
int a[501];
int d[501][501];
// D[i][j] = i번 파일부터 j번 파일까지 합치는 최소 비용
// i <= k < j
// D[i][k] + D[k+1] + 파일 합치는 비용
using namespace std;

int go(int i, int j)
{
    if (i == j)
        return 0;
    if (d[i][j] != -1)
        return d[i][j];
    int sum = 0;
    int &ans = d[i][j];
    for (int k = i; k <= j; k++)
    {
        sum += a[k];
    }
    for (int k = i; k < j; k++)
    {
        int temp = go(i, k) + go(k + 1, j) + sum;
        if (ans == -1 || ans > temp)
        {
            ans = temp;
        }
    }
    return ans;
}

int main()
{
    int t;
    cin >> t;
    while (t--)
    {
        memset(d, -1, sizeof(d));
        int n;
        cin >> n;
        for (int i = 1; i <= n; i++)
        {
            cin >> a[i];
        }
        cout << go(1, n) << '\n';
    }
}

재귀적으로 풀 수 있는데, 파일을 k를 기준으로 쪼개서 비용을 지속적으로 추가해주면서 최솟값을 구하는 과정입니다. 

 

D[i][k] + D[k+1][j] + 비용 과 같이 점화식을 세울 수 있습니다.