백준 11066 / 파일 합치기

연속 연속 연속 연속

다이내믹프로그래밍 문제

D[i][j]를 i부터 j까지 파일을 하나로 합치는데 드는 최소 비용이라고 하자.

메인 로직은 

i부터 j 사이에 있는 어느 k에 대해

D[i][j] = min( D[i][j], D[i][k] + D[k+1][j] + i부터 j까지 다합친 크기) 이다.

여기서 최소값이기 떄문에 D를 연산에 들어가기 전 최대값으로 초기화해주어야한다.

i부터 j까지 다 합친 크기를 한번 더 더해주는 이유는 i-k부터 끊고 k+1-j까지 끊은 걸 합쳐줄 떄 비용이 발생하기 떄문.

for문으로 풀기엔 case 정의가 어려워 재귀로 풀어야한다.

코드

#include<stdio.h>
#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
 
using namespace std;
 
 
int sum[501];
int d[501][501];
int arr[501];
 
 
int init() {
    for (int i = 0; i < 501; i++) {
        sum[i] = 0;
        arr[i] = 0;
        for (int j = 0; j < 501; j++) {
            d[i][j] = -1;
        }
    }
    return 0;
}
 
 
int go(int start, int end) {
 
    if (end == start + 1) {
        
        return arr[end] + arr[start];
    }
    if (end == start) {
        return 0;
    }
    if (d[start][end] != -1) {
        return d[start][end];
    }
    
    d[start][end] = 2000000000;
 
    for (int i = start; i <= end; i++) {
        d[start][end] = min(d[start][end], go(start, i) + go(i + 1, end) + sum[end] - sum[start - 1]);
    }
 
    return d[start][end];
}
 
int main() {
    
    //freopen("Text.txt", "r", stdin);
 
    int testcase;
    cin >> testcase;
 
    while (testcase--) {
 
        int n;
        cin >> n;
        
        init();
    
        for (int i = 0; i < n; i++) {
            cin >> arr[i];
 
            if (i == 0) {
                sum[i] = arr[i];
            }
            else {
                sum[i] += sum[i - 1] + arr[i];
            }
 
            
        }
 
        cout << go(0, n - 1)<<endl;
 
    }
 
}

어렵다. 어려워..