BOJ 11066 Merging Files(파일 합치기)

 

문제 링크 : https://www.acmicpc.net/problem/11066

11066번: 파일 합치기

 

비교적 쉬운 문제들부터 Top-Down 구현과  Bottom-Up 구현을 비교해 보고 있는데,

부족한 것이 한둘이 아니다.

 

이 문제에서는 두 구현에 같은 사고 방식을 적용하지 못했다.

따라서 시간 비교는 별 의미는 없지만 Top-Down 방식이 4 배 이상의 시간을 소요한다.

 

recur( a , b ) 함수는 구간 [ a , b ] 에서 최적의 순서(최소 비용)로 결합한 비용을 돌려준다.

 

 

탑다운 방식이 코드 작성이 내게는 편하다.

기저 사례에 대한 처리만 선행되면 그 뒤는 알아서 잘 하겠거니 하면 된다. 

 

#include<bits/stdc++.h>

using namespace std;

int n,arr[501];
int ss[501],dp[501][501];

int recur(int a, int b){
    if(a==b) return 0;
    int &ret=dp[a][b];
    if(ret) return ret;
       
    ret=INT_MAX;
    for(int i=a;i<b;i++){
        ret=min(ret, recur(a,i)+recur(i+1,b));
    }
    ret+=ss[b]-ss[a-1];
    return ret;
}

void solve(){
    memset(dp,0,sizeof dp);
    scanf("%d",&n);
    for(int i=1;i<=n;i++) {
        scanf("%d", &arr[i]);
        ss[i]=ss[i-1]+arr[i];
    }

    printf("%d\n",recur(1,n));
}

int main(){
    int T; scanf("%d",&T);
    while(T--){
        solve();
    }
}

 

바텀업 방식은 부분 문제를 길이 순으로 해결한다.

길이가 2 일 때를 해결하고 3, 4, ... 인 경우를 차례로 해결한다.

 

#include<bits/stdc++.h>

using namespace std;

int n,arr[501];
int ss[501],dp[501][501];

void solve(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&arr[i]);
        ss[i]=ss[i-1]+arr[i];
    }

    for(int l=2;l<=n;l++){
        for(int i=1;i<=n-l+1;i++){
            int j=i+l-1;
            dp[i][j]=INT_MAX;
            for(int k=i;k<j;k++){
                dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]);
            }
            dp[i][j]+=ss[j]-ss[i-1];
        }
    }
    printf("%d\n",dp[1][n]);   
}

int main(){
    int T; scanf("%d",&T);
    while(T--){
        solve();
    }
}