[C++] BAEKJOON 11066 파일합치기

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

11066번: 파일 합치기

동적계획법을 사용하여 문제를 해결하였습니다 . 그 중에서도 top-down 방식입니다.

dp[i][j] 는 i 부터 j 까지의 파일을 합치는 최소 비용 으로 정의했습니다.

파일의 사이즈를 중복해서 더해줘야 하므로 sum 배열을 만들어 구간까지의 파일의 합을 한 번에 더해 줄 수 있게 하였습니다.

#include <iostream>
#include <cstring>

using namespace std;

int file[501];
int sum[501];
int dp[501][501];

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

int main(){
    int T;
    cin >> T;
    for (int t=0;t<T;t++){
        memset(dp,-1,sizeof(dp));
        memset(sum,0,sizeof(sum));
        
        int N;
        cin >> N;
        
        for (int i=1;i<=N;i++){
            cin >> file[i];
            sum[i] = sum[i-1] + file[i];
        }
        
        cout << go(1,N) <<"\n";
    }
    return 0;
}