11066번(다시풀기)

11066번 - 파일 합치기

풀려고 생각하다가 못 풀어서 결국 구글링을 보고 해결했다. 다시 풀어볼 문제

D[i][j] 는 i 에서 j 까지 파일을 합칠 때 가장 최솟값

D[i][j] = D[i][k] + D[k+1][j] + sum[j]-sum[i-1] (i~j까지의 합)

이라는 점화식으로 문제를 풀 수 있었다.

이때 i 와 j 가 같다면, 자기 자신이기 때문에 더할 필요가 없게 되고, 

i와 j의 차이가 1일때는 두 값의 합을 리턴하게 된다.

<정답 코드>

#include<iostream>
#include<algorithm>
using namespace std;
 
const int INF = 2100000000;
int A[501];
int D[501][501];
int sum[501];
int n;
void init()
{
    for (int i = 0; i < 501; i++)
    {
        A[i] = 0;
        sum[i] = 0;
        for (int j = 0; j < 501; j++)
        {
            D[i][j] = -1;
        }
    }
}
 
int go(int s, int e)
{
    if (e == s + 1)
    {
        return A[s]+A[e];
    }
 
    if (s == e)
    {
        return 0;
    }
 
    if (D[s][e] != -1)
    {
        return D[s][e];
    }
 
    D[s][e] = INF;
 
    for (int i = s; i <= e; i++)
    {
        D[s][e] = min(D[s][e], go(s, i) + go(i + 1, e) + sum[e] - sum[s - 1]);
    }
 
    return D[s][e];
 
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int tc;
    cin >> tc;
 
    for (int t = 1; t <= tc; t++)
    {
        
        cin >> n;
        init();
        for (int i = 0; i < n; i++)
        {
            cin >> A[i];
            if (i != 0)
            {
                sum[i] += sum[i - 1] + A[i];
            }
            else
            {
                sum[i] = A[i];
            }
        }
 
 
        cout << go(0, n - 1) << "\n";
    }
 
    return 0;
}