백준 11066 / C++

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

11066번: 파일 합치기

 

0. 전체적인 접근

 

파일을 연속적으로 합쳐야 하는게 파일합치기3 문제와 다른 점이다. 

dp[i][j]를 i부터 j까지 합친 최솟값이라 하자. 연속적으로 합쳐야 하므로.. i<k<j인 k에 대해 

dp[i][j]는 dp[i][k]와 dp[k+1][j]를 통해 만들어진다. 

따라서 dp[i][j]=min(dp[i][k]+dp[k+1][j]+sum[i,j])로 구해줄 수 있다. 

(두 값을 합친 후 둘이 더하는 값이 i부터 j번까지 합이 됨을 관찰하자)

이 문제는 탑다운으로 작성하는게 간단하다. 하지만 바텀업 방식이 좀 까다롭지만 공부할 필요가 있다.

 

1. 탑다운 

우선 탑다운 재귀식 코드는 그냥 하던대로 하주면 된다. 

 

[ Code 1 ]

#include <bits/stdc++.h>
using namespace std;
int a[505], psum[505], dp[505][505];

// dp[s][e]=min(dp[s][m]+dp[m+1][e]+sum[s,e])
int go(int s, int e) {
    if (s == e) return 0;
    int& ret = dp[s][e];
    if (ret != -1) return ret;
    ret = 1e9;
    for (int m = s; m < e; m++) {
        ret = min(ret, go(s, m) + go(m + 1, e) + psum[e] - psum[s - 1]);
    }
    return ret;
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int tc; cin >> tc;
    while (tc--) {
        int n; cin >> n;
        for (int i = 1; i <= n; i++) {
            cin >> a[i];
            psum[i] = psum[i - 1] + a[i];
        }
        memset(dp, -1, sizeof(dp));
        cout << go(1, n) << '\n';
    }
}

 

 

 

2. 바텀업 

dp[i][j]=min(dp[i][k]+dp[k+1][j]+sum[i,j]) 에서 값을 갱신할 때 항상 갱신의 순서에 유의해야 한다.

만약 위 식을  for(i=1~n)

                          for(j=i~j<=n)

                                for(k=i~k<j) 

위와 같이 갱신하면 dp[i][j]를 갱신할 때 dp[k+1][j]가 갱신되지 않고 있다. i가 k+1까지 돌아야 비로소 갱신되기 때문.

구간 순으로 순회하면 올바르게 갱신이 됨을 알 수 있다. [i,j] 길이가 [i, k]와 [k+1,j]  보다 항상 크므로..   

 

 

 

[ Code 2 ]

#include <bits/stdc++.h>
using namespace std;
int tc, n, a[505], psum[505], dp[505][505];

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> tc;
    while (tc--) {
        cin >> n;
        for (int i = 1; i <= n; i++) {
            cin >> a[i];
            psum[i] = psum[i - 1] + a[i];
        }
        for (int i = 1; i <= n; i++) { // 길이
            for (int j = 1; j + i <= n; j++) { // 인덱스
                dp[j][i + j] = 1e9;
                int sum = psum[i + j] - psum[j - 1];
                for (int k = j; k < i + j; k++) {
                    dp[j][i + j] = min(dp[j][i + j], dp[j][k] + dp[k + 1][i + j] + sum);
                }
            }
        }
        cout << dp[1][n] << '\n';
    }
}