BOJ 11066 파일 합치기

www.acmicpc.net/problem/11066

11066번: 파일 합치기

 

파일을 합칠 수 있는데 합치는데 드는 비용의 누적 합 중 최소가 되는 값이 정답이 된다.

재귀적으로 접근하면 그나마 쉽게 해 볼 수 있는데 그래도 어렵다..

 

위 사진처럼 진행하는데

 

임시파일이나 원래의 파일을 계속 두 개씩 합쳐서 소설의 여러 장들이 연속이 되도록 파일을 합쳐나가고, 최종적으로는 하나의 파일로 합친다

 

연속이 되야 하기 때문에 따로 정렬이나 부분을 나누어서 접근하면 틀린다.

 

d [i][j]를 i ~ j 구간의 최소합이라고 하면

1부터 n 까지의 구간합 중 최소가 정답이 된다.

 

 

#include <iostream>
#include <algorithm>
using namespace std;
 
const int inf = 1e9;
int pSum[501], d[501][501];
int t, n, a[501];
 
int f(int s, int e) {
    if (s == e) return 0;
    if (s + 1 == e) return d[s][e] = a[s] + a[e];
    if (d[s][e] != inf) return d[s][e];
 
    for (int i = s; i <= e; ++i)
        d[s][e] = min(d[s][e], f(s, i) + f(i + 1, e));
 
    return d[s][e] += pSum[e] - pSum[s - 1];
}
 
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
 
    cin >> t;
    while (t--) {
        fill(&d[0][0], &d[500][501], inf);
 
        cin >> n;
        for (int i = 1; i <= n; ++i)
            cin >> a[i], pSum[i] = pSum[i - 1] + a[i];
 
        cout << f(1, n) << '\n';
    }
 
    return 0;
}

 

우선 2개로 나뉠 때까지 쪼개 주고, 2개로 나뉘었다면 그 두 합을 더해준다.

이후 반복문을 통해 mid값을 s와 e 사이에서 돌려보면서 그중에서 최소가 되는 값을 찾는다

우리가 원하는 값은 모든 누적값이기 때문에 return 할 때에 구간 합을 더해줘서 반환해줘야 한다.