[BOJ] 11066번 : 파일 합치기 (C++)

문제 링크 : 백준 11066번

[문제 접근]

풀이 방법을 생각하지 못해서 다른 풀이를 참고했다.

dp[x][y] : x~y 번째 파일들을 합치는데 필요한 최소 비용
sum[x] : 1~x 번째 파일까지 크기들의 합

3중 for문으로 O(n^3)이 걸린다.

1. for문에서 i는 구해야하는 범위를 의미한다.
   ex) i=2 이면 1~3번째 파일, 2~4번째 파일 등을 합친다는 것을 의미
2. x는 합치는 범위의 시작을 의미한다.
   i가 범위를 의미하므로 k-i까지만 해주면 k까지 탐색하게 된다.
3. mid는 구해야하는 범위를 두 부분으로 나누는 기준점을 의미한다.
   ex) dp[3][6]을 구하는 상황이면 범위를 뜻하는 i는 3이고, 범위의 시작인 x는 3이다.
   그리고 mid에 따라
   {[3] / [4,5,6]}
   {[3,4] / [5,6]}
   {[3,4,5] / [6]}
   으로 나누면서 모든 경우 수의 비용을 비교하고 그 중 최소를 dp[3][6]에 저장한다.
4. dp[n][n]은 0이기 때문에 sum을 이용해 dp를 갱신해줄 수 있다.
   ex) dp[1][2]는 [1] / [2]로 하나의 경우의 수 밖에 없기 때문에 dp[1][1] + dp[2][2] + sum[2]-sum[0]가 최소 비용이다. 즉, 1~2번째 파일을 합한 값이 최소비용이다.

위의 방식에 따라 계속 최소 비용을 갱신시켜주고 결과적으로 dp[1][k]가 1~k 번째 파일들을 합치는데 필요한 최소 비용이기 때문에 정답으로 출력해주면 된다.

[소스 코드]

#include <iostream>
#include <algorithm>
#include <limits.h>

using namespace std;
int t;
int dp[501][501];
int sum[501];

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);    
    cin >> t;
    while(t--) {
        int k;
        cin >> k;
        for(int i=1 ; i<=k ; i++) {
            int a;
            cin >> a;
            sum[i] = sum[i-1] + a; // 1~x 번째 파일까지의 크기 합
        }
        
        for(int i=1 ; i<k ; i++) { // i는 구해야하는 범위를 의미 -> ex. i=1이면 1~2번째 파일 등을 합칠 때를 의미
            for(int x=1 ; x<=k-i ; x++) { //x는 합치는 범위의 시작 부분을 의미 -> i가 범위를 의미하므로 k-i까지만 해주면 k까지 탐색하게 된다.
                int y = x+i;
                dp[x][y] = INT_MAX; // x~y 번째 파일들을 합치는데 필요한 최소 비용

                for(int mid = x ; mid<y ; mid++) { // mid는 구해야하는 범위를 두 부분으로 나누는 기준점을 의미
                    dp[x][y] = min(dp[x][y], dp[x][mid] + dp[mid+1][y] + sum[y] - sum[x-1]);
                    // dp[n][n]은 0이기 때문에 sum[y] - sum[x-1]로 dp[x][y]를 갱신
                }
            }
        }
        cout << dp[1][k] << "\n";
    }
    return 0;
}