[백준/C++] #11066 파일 합치기 (DP)

문제

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

 

구상

문제 풀이가 생각이 안나면 나는 일단 DP로 접근을 해본다. 이 문제도 그러했는데, DP로 접근해보니 풀이가 보였다. 이전 합치는 비용을 이용해서 다음 합치는 비용을 구했다. DP를 사용할 때는 획일화된 기준이 중요해서 첫 기준을 파일 길이로 잡고 다음 기준을 파일 시작 위치로 정했다. 그랬더니 파일 끝 위치는 저절로 설정할 수 있었고, 다음 기준을 분할 위치로 잡았다. 그렇게 마지막 식을 보면 알 수 있듯이 이전 값들을 이용해서 보다 큰 다음 비용을 구할 수 있었다. 

알고리즘

이전 합치는 비용 이용해서 다음 합치는 비용을 구하니까 DP를 이용했다. 

 

풀이 + 코드

dp[i][j]: 파일 i부터 j까지 합치는 데 필요한 최소 비용.
sum[i][j]: 파일 i부터 j까지의 파일 크기의 합.

#include<iostream>
#include<vector>
#include<algorithm>
#include<climits>
#include<queue>
#define INF 987654321
#define endl "\n"
using namespace std;
/*
11066 파일 합치기
파일의 크기가 주어졌을 때, 파일들을 하나의 파일로 합칠 때 필요한 최소비용을 계산하자
*/

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

    int T;
    cin >> T;
    while (T--) { // 테케 수
        int K;
        cin >> K; // 챕터 수

        vector<int> files(K);
        vector<vector<int>> dp(K, vector<int>(K, INF));
        vector<vector<int>> sum(K, vector<int>(K, 0));

        // 초기화
        for (int i = 0; i < K; i++) {
            cin >> files[i];
            sum[i][i] = files[i]; // 파일 i부터 i까지 합치는데 필요한 최소 비용은 해당 파일의 크기
            dp[i][i] = 0; // 한개의 파일을 합치는 비용은 0
        }

        // sum[i][j] 구하기
        for (int i = 0; i < K; i++) {
            for (int j = i + 1; j < K; j++) {
                sum[i][j] = sum[i][j - 1] + files[j];
            }
        }

        // 두 파일을 합치는 최소 비용을 계산하기 위해 모든 가능한 파일 쌍을 탐색
        for (int length = 2; length <= K; length++) {  // 파일 길이를 기준으로 2부터 K까지 증가시키기
            for (int i = 0; i <= K - length; i++) { // 각 파일 길이에 대해 가능한 모든 시작 지점 i를 탐색
                int j = i + length - 1; // 탐색 끝 지점 j
                for (int k = i; k < j; k++) { // 어떤 시점에서 두 부분으로 나눌지 결정하는 인덱스 k
                    dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j] + sum[i][j]); // 가능한 모든 k를 탐색하여 최적의 분할점을 찾기
                    // dp[i][k]와 dp[k+1][j]는 각각의 구간을 합치는 최소 비용
                    // sum[i][j]은 이 두 구간을 합친 후, 다시 두 부분을 합치는 비용
                }
            }
        }

        cout << dp[0][K - 1] << endl; // 합치는 최소비용
    }

    return 0;
}