(11066) 파일 합치기

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

단계별로 풀어보기

31단계(동적 계획법 2) 1번째

 

 

 

돌아온 동적계획법. 1과는 비교도 안되게 어렵다.

dp[a][b]를 a번 파일부터 b번 파일까지 합칠 때 최소 비용이라고 하자.

이때 a~b파일을 만드려면 a≤m<b인 m에 대해 a~m파일과 m+1~b파일을 합쳐야 한다.

a~m파일의 비용은 dp[a][m], m+1~b파일의 비용은 dp[m+1][b]이고, 두 파일을 합칠 때 필요한 비용은 a부터 b파일까지 크기의 합인데 이건 누적합 배열로 빠르게 구할 수 있다. 이것을 a≤m<b인 모든 m에 대해 탐색하여 최솟값을 dp[a][b]에 저장하면 된다.

 

 

 

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

int solve(){
  int n;
  
  cin >> n;
  
  vector<int> s(n+1);
  vector dp(n+1, vector<int> (n+1));
  
  for(int i=1;i<=n;i++){
    cin >> s[i];
    s[i]+= s[i-1];
  }
  
  for(int i=1;i<n;i++){
    for(int j=1;j+i<=n;j++){
      dp[j][j+i]= INF;
      
      for(int k=j;k<j+i;k++){
        dp[j][j+i]= min(dp[j][j+i], dp[j][k]+dp[k+1][j+i]+s[j+i]-s[j-1]);
      }
    }
  }
  
  return dp[1][n];
}

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