Baekjoon 11066번 파일 합치기

문제

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

걸린 시간

-

풀이

C++

#include <bits/stdc++.h>
#define INF 1e9
#define all(c) c.begin(), c.end()
typedef long long ll;
typedef unsigned long long ull;
using namespace std;

int C[501];
int X[501][501];
int cache[501][501];

int dp(int s, int e){
    // 기저 사례
    if(s == e) return 0;
    // 메모이제이션
    int& ret = cache[s][e];
    if(ret != -1) return ret;
    // 재귀 함수
    ret = INF;
    for(int m = s; m < e; m++)
        ret = min(ret, dp(s, m) + dp(m+1, e));
    return ret += X[s][e];
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int tc;
    cin >> tc;
    while(tc--){
        int k;
        cin >> k;
        for(int i = 1; i <= k; i++)
            cin >> C[i];
        memset(cache, -1, sizeof(cache));
        memset(X, 0, sizeof(X));
        for(int i = 1; i <= k; i++)
            X[i][i] = C[i];
        for(int i = 1; i <= k; i++)
            for(int j = i+1; j <= k; j++)
                X[i][j] = X[i][j-1] + C[j];
        cout << dp(1, k) << "\n";
    }
    return 0;
}

파일의 크기 C 를 입력받으면 행과 열을 각각 파일의 시작 s 과 끝 번호 e 로 하는 2차원 임시파일 배열 X 를 구해둔다.

X 행열은 s번 부터 e번 까지 파일을 합칠 때 드는 비용을 의미한다. 각 범위의 비용은 합쳐진 파일 각각의 비용을 모두 더한 값이므로 쉽게 구할 수 있다.

이 문제는 최적화 기법을 적용하기 전에 완전탐색으로 모든 경우를 조사할 수 있어야 한다.

항상 인접한 두개의 파일을 합쳐나간다는 사실로부터 각 단계마다 하나의 파일을 두개의 파일로 나누어나가도록 거꾸로 접근할 경우, 아까 구해 놓았던 X 행열의 값을 이용하여 하나의 파일로 합칠 때 드는 최소 비용을 구할 수 있다.

하지만 빨간 동그라미 부분처럼 중복계산되는 구간이 발생한다. s ~ e 범위의 파일을 합치는데 드는 최소 비용을 메모이제이션하면 중복을 없앨 수 있다.

풀이가 대부분 비슷할 줄 알았는데 생각했던 것 보다 다양한 방법이 있어 아래에 첨부했다.

참고

[백준] 11066번 C/C++ 풀이 _ 파일 합치기 - Easy is Perfect