C++ 백준 11066 (파일 합치기)

백준 11066 (파일 합치기)

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

11066번: 파일 합치기

---

전형적인 DP식 문제이다.

 

문제들을 풀면서 느낀 점인데 뭔가 문제를 보고 딱 떠오르는 알고리즘이 없으면 구현/DP인 것 같다.

 

 

설명

---

2차원 DP를 선언한다.

dp[i][j]는 i부터 j파일까지 합쳤을 때 최소비용이다.

 

그렇게 되면

d[i][i] = 파일 i의 크기가 될 것이다.

 

아이디어는 다음과 같다.

i~j까지의 파일을 합치는데 해당 파일들이 합쳐지기 전에는 특정 지점에서 나뉘어 졌을 것이다.

 

무슨말이냐면 i~j 사이의 한 점을 m이라고 하면

파일 i~j는 파일 i~m 과 파일 m+1~j가 합쳐져 생긴 것이다.

 

즉 i~j 사이에 있는 한 지점을 찾아 그 비용이 최소가 되게하면 될 것이다.

 

dp[i][j] = dp[i][m]+dp[m+1][j]+(i~m까지의 파일 합)+(m+1~j까지 파일 합)

파란 부분을 잘 보자. m이 어디에 있든 파란 부분의 값은 절대 변하지 않는다.

 

즉 dp[i][j] = dp[i][m] + dp[m+1][j] + sum(i~j) (i~j까지 파일 합)

dp[i][j]가 최소가 되는 m값을 찾으면 된다.

 

구현

---

#include <iostream>
#include <algorithm>
using namespace std;
int n,a;
int dp[501][501];
int sum[501];

int main(){
    ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
    sum[0]=0;
    int t;
    cin>>t;
    for(int ca=0;ca<t;ca++){
        cin>>n;
        for(int i=1;i<=n;i++){
            cin>>a;
            sum[i]=sum[i-1]+a;
        }
        
        for(int k=1;k<n;k++){
            int i=1;
            int j=k+1;
            for(int u=0;u<n-k;u++){
                dp[i][j]=1e9;
                for(int m=j-k;m<=j-1;m++){
                    dp[i][j]=min(dp[i][j],dp[i][m]+dp[m+1][j]+sum[j]-sum[i-1]);
                }
                i++;
                j++;
            }
        }
        
        cout<<dp[1][n]<<"\n";
    }
    return 0;
}