[Baekjoon,11066]파일 합치기

해결

초기에는 최단거리 알고리즘을 생각했으나 500개의 정점을 하나씩 줄이며 진행하기에는 너무 많은 양이어서 다른 방법을 찾아야 했다. 현재 파일과 다음 파일 중 합치거나 안 합치거나 진행해보려 했으나 진전이 없었다. 그렇게 찾아보던 중 이곳에서 알게 된 방법이 있었다.

파일이 하나가 될 때 까지 나누자

왼쪽 인덱스 lo와 오른쪽 인덱스 hi가 있을 때 구간 [lo,hi]의 최소합을 메모이제션을 이용해 구하는 함수를 만들면 된다. 현재 파일을 가운데 mid를 기준으로 나누어 쪼개다가 파일이 하나가 되면 합칠 수 없으니 0을 반환한다. 파일이 2개라면 둘을 합친 값을 반환한다. 파일이 3개가 넘어가면 2+1 혹은 1+2로 쪼개어 계산한 것 중 더 작은 값을 취한다. 이때 결과값으로는 합친 모든 비용을 더해야 하니 결과 값에 해당 구간의 합을 부분 합을 이용하여 더해준다.

예를 들어 2+1로 쪼갠 3개가 있는 파일의 최소 합을 생각해 보자.

• 최소 합 = 2를 합칠 때 만들어진 비용 + 남은 파일 1개를 2와 합친 비용

이렇기 때문에 구간의 합을 더해주는 것이다. 이제 여기서 lo, hi가 정해졌을 때 값을 cache에 저장하면 중복되는 계산을 없앨 수 있다. 구현 시 부분합을 미리 구해놓아 구간의 합을 쉽게 구하고 있으며, 부분합에 쉽게 접근하기 위해 인덱스를 1부터 시작하는 것을 눈여겨 보자.

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;

const int INF=987654321;
const int MAX=501;

int n;
int cost[MAX],psum[MAX];
int cache[MAX][MAX];

int solve(int lo, int hi) 
{
    // 메모이제이션
    int& ret=cache[lo][hi];
    if(ret!=-1)
        return ret;
    // 한 칸이면 더할 수 없으니 0을 반환 
    if(lo==hi)
        return ret=0;
    // 둘이 되어 합칠 수 있으면 
    if(lo+1==hi)
        return ret=cost[lo]+cost[hi];
    // 분할 탐색한다.
    ret=INF;
    for(int mid=lo;mid<hi;++mid)
    {
        int left=solve(lo,mid);
        int right=solve(mid+1,hi);
        ret=min(ret,left+right);
    }
    return ret+=psum[hi]-psum[lo-1];
}

int main()
{
    int testCase;
    cin>>testCase;
    while(testCase--)
    {
        cin>>n;
        psum[0]=0;
        for(int i=1;i<=n;++i)
        {
            scanf("%d",&cost[i]);
            psum[i]=psum[i-1]+cost[i];
        }
        memset(cache,-1,sizeof(cache));
        
        cout<<solve(1,n)<<endl;
    }

    return 0;
}

다른 방법

직관적이지는 않지만 Bottom-up 방식으로 구현하면 재귀를 위한 함수가 없어 속도가 더욱 빠르다. 이곳에서 풀이2 를 보면 알 수 있다.