[BOJ 11066] 파일 합치기

11066번: 파일 합치기

1. 문제 설명

 

2. 구현 아이디어 1 - 맞았습니다!!

처음에는 빡구현 문제라고 생각하여 규칙을 찾아내고자 애를 썼지만 잘 되지 않았다 😥

결국 다른 사람의 코드를 참고하였고, DP로 풀어야 하는 문제임을 알 수 있었다.

 

DP 배열은 2차원 배열로, DP[i][j]는 i번째부터 j번째 파일을 합치는데 필요한 최소 비용을 의미한다.

 

파일을 합치기 전에는 특정 지점을 기준으로 파일이 나누어져있을 것이다. (like 분할정복에서 합치기 전에 나뉘었던 것처럼 ...)

해당 지점을 l이라고 했을 때, i~j번째 파일을 합친 비용 = (i~l번째 파일을 합친 비용) + (l~j번째 파일을 합친 비용) 이다.

 

이를 참고하여 아래와 같이 DP 점화식을 구할 수 있다.

* sum[i] = 1~i번째 파일 크기의 합

dp[i][j] = min(dp[i][j], dp[j][l]+dp[l+1][i+j]+sum[i+j]-sum[j-1])

 

3중 반복문을 사용해 l을 i와 j 사이에서 변경해가며 min 함수로 현재 DP 값과 비교하며 최소 비용을 찾아주면 된다.

 

#include <bits/stdc++.h>

using namespace std;

#define INF 987654321

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int t;
    cin >> t;

    while (t--) {
        int k;
        cin >> k;

        vector<int> chapters = vector<int>(k+1, 0);
        vector<int> sum = vector<int>(k+1, 0);
        vector<vector<int>> dp = vector<vector<int>>(k+1, vector<int>(k+1, 0));
        for (int i = 1; i <= k; ++i) {
            cin >> chapters[i];
            sum[i] = sum[i-1] + chapters[i];
        }

        for (int i = 1; i <= k; ++i) {
            for (int j = 1; j <= k-i ; ++j) {
                dp[j][i+j] = INF;
                for (int l = j; l < i+j; ++l) {
                    dp[j][i+j] = min(dp[j][i+j], dp[j][l]+dp[l+1][i+j]+sum[i+j]-sum[j-1]);
                }
            }
        }

        cout << dp[1][k] << "\n";
    }
}