[백준 11066] 알고리즘 94일차 : 파일 합치기

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

 

11066번: 파일 합치기

동적계획법

 

핵심 로직

dp[i][j] = dp[i][mid]+dp[mid+1][j] + 누적합(최상위 노드값)

3중 for문을 도는데

첫번째 반복문은 gap 그러니까 범위다 start~end 범위 크기를 1부터 chapter수인 K-1개까지 반복한다. (그럼 마지막 반복문을 돌면 0~K-1까지를 구할 수 있음)

두번째 반복문은 start~end범위 내에서 start의 위치를 한칸씩 뒤로 옮기면서 계산하는 것이다. (gap이 3인 상태에서 0~3였다면 다음은 1~4) 구간이동 정도라고 이해하면 된다. 이 반복문에선 dp[start][end]값을 결정하게 된다.

세번째 반복문은 이제 start~end범위가 fix된 상태이다. 여기서 dp[start][end]에 들어갈 최솟값을 구하는 작업을 하는 반복문이다.

여기서 이 점화식을 사용한다. dp[i][j] = dp[i][mid]+dp[mid+1][j] + 누적합(최상위 노드값)

세번째 반복문에선 mid값을 start부터 end-1까지 이동시키면서 dp[start][end]의 최솟값을 구하여 대입한다.

dp[i][mid]+dp[mid+1][j] + 누적합(최상위 노드값) 이 값과 기존의 dp[i][j]를 비교하며 최솟값으로 갱신한다.

누적합을 더하는 이유는 어떤상태에서건 최상위 노드(그 범위내에서의 모든 chapter를 묶은 가장 최근 비용)은 그 범위내의 모든 chapter의 크기를 합한것이기 때문.

 

모든 반복문을 나와서 dp[0][K-1]를 출력하면 끝

세번째 반복문 부분은 하나씩 따라가면서 해봐야 그나마 이해가 된다.

 

...

문제 내용이 재밌어서 괜찮을줄알았는데 처음에 짠로직 틀려서 뒤엎음...

dp정복하기에 갈길이 멀구나 ^_^

 

소스코드

#include <iostream>
#include <climits>
using namespace std;

int dp[500][500];
int sum[500];
int page[500];
int main(){
    int T;
    cin >> T;
    
    for(int t = 0 ; t < T ; t++){
        int K;
        cin >> K;
        
        for(int k = 0 ; k < K ; k++){
            cin >> page[k];
            if(k == 0)
                sum[k] = page[k];
            else
                sum[k] = sum[k-1] + page[k];
        }
        
        for(int gap = 1 ; gap < K ; gap++){
            for(int start = 0; start + gap < K ; start++){
                int end = start + gap;
                dp[start][end] = INT_MAX;
                for(int mid = start ; mid < end ; mid++){
                    dp[start][end] = min(dp[start][end], dp[start][mid] + dp[mid+1][end] + sum[end]-sum[start-1]);
                }
            }
        }
        cout << dp[0][K-1] << "\n";
    }
    
    return 0;
}