(13974) 파일 합치기 2

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

단계별로 풀어보기

62단계(동적 계획법 최적화 1) 9번째

 

 

 

파일 합치기 문제인데 N의 범위가 커져서 크누스 최적화를 써야 하는 문제.

dp[i][j]= min(dp[i][k]+dp[k+1][j])+C[i][j] (i≤k<j) 형태의 점화식을 특정 조건에서 O(N^3)에서 O(N^2)으로 줄일 수 있는 최적화 방법이다.

이때 특정 조건은 a≤b≤c≤d에 대해 C(b,c)≤C(a,d)를 만족하고(단조성) C(a,c)+C(b,d)≤C(a,d)+C(b,c)를 만족해야 한다(사각부등식) dp[i][j]가 최소일 때 k값을 opt[i][j]라고 하자. 그러면 opt[i][j-1]≤opt[i][j]≤opt[i+1][j]이 성립한다. 이 범위는 i≤k<j에 비해 훨씬 작기 때문에 거의 상수 시간에 k값을 찾아낼 수 있다.

그렇게 어렵진 않은데 쓰임처가 굉장히 제한적이다. 백준에서 크누스 최적화로 검색해도 나오는 문제가 두 페이지를 못 채우는 걸로 기억한다.

 

 

 

#include <iostream>
#include <vector>
#define INF 2000000000
using namespace std;

int solve(){
  int k;
  cin >> k;
  
  vector<int> cost(k+1), sum(k+1);
  vector dp(k+1, vector<int> (k+1, INF));
  vector opt(k+1, vector<int> (k+1, 0));
  
  for(int i=1;i<=k;i++){
    cin >> cost[i];
    sum[i]= sum[i-1]+cost[i];
    dp[i][i]= 0;
    opt[i][i]= i;
  }
  
  for(int i=1;i<k;i++){
    for(int j=1;j+i<=k;j++){
      for(int l=opt[j][j+i-1];l<=min(j+i-1,opt[j+1][j+i]);l++){
        int newcost= dp[j][l]+dp[l+1][j+i]+sum[j+i]-sum[j-1];
        if(newcost<=dp[j][j+i]){
          dp[j][j+i]= newcost;
          opt[j][j+i]= l;
        }
      }
    }
  }
  
  return dp[1][k];
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  
  int T;
  
  cin >> T;
  
  while(T--){
    cout << solve() << "\n";
  }
  
  return 0;
}