BOJ 11066번 :: 파일 합치기

#문제

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

11066번: 파일 합치기

 

#작성 코드

#include <iostream>
using namespace std;
 
int t, k;
int ch[501];        // 각 챕터별 파일 사이즈 저장. 인덱스 1~k사용 
int d[501][501]; 
int sum[501];
int INF = 987654321;
int main(){
    cin>>t;
    while(t--){
        cin>>k;
        
        for(int i=1; i<=k; i++){
            cin>>ch[i];
            sum[i] = sum[i-1]+ch[i];
        }
        
        for(int i=1; i<k; i++){            // i : 1 ~ k-1
            for(int a=1; a+i<=k; a++){
                int b = a+i;
                d[a][b] = INF;
                
                for(int mid = a; mid<b; mid++){        // mid : a ~ b-1까지 
                    d[a][b] = min(d[a][b], d[a][mid]+d[mid+1][b]+sum[b]-sum[a-1]);
                                                            // ch[a] + ch[a+1] + ... + ch[b]
                }
            }
        }
        cout<<d[1][k]<<'\n'; 
    }
    return 0;
}

코드2

#include <iostream>
using namespace std;
 
int t, k;
int dp[501][501];
int ch[501];
int sum[501];
int INF = 987654321;
 
int cal(int x, int y){
    if( dp[x][y] != INF ){
        // ch[x] ~ ch[y]까지 합치는 비용 계산된적있다면 return 
        return dp[x][y];
    }
    if( x==y ){
        // ch[x] ~ ch[x] 합치는 비용은 0 
        return dp[x][y] = 0;
    }
    if( x+1==y ){
        // ch[x] ~ ch[x+1] 합치는 비용은 두 파일의 크기 합 
        return dp[x][y] = ch[x]+ch[x+1];
    }
    
    // 어느 부분을 기준으로 이 구간을 두 부분으로 나누는 것이 좋을까
    // ch[x]~ch[mid] + ch[mid+1]~ch[y] 합치는 비용 최솟값 업데이트. 
    for(int mid=x; mid<y; mid++){
        int leftmin = cal(x, mid);
        int rightmin = cal(mid+1, y);
        dp[x][y] = min(dp[x][y], leftmin+rightmin);
    }
    return dp[x][y] += sum[y]-sum[x-1];
}
 
int main(){
    cin>>t;
    while(t--){
        cin>>k;
        for(int i=1; i<=k; i++){
            cin>>ch[i];
            sum[i] = sum[i-1]+ch[i];        // ~ch[i]까지의 누적합 sum[i]에 저장 
        }
        
        // dp[][]를 모두 INF로 초기화. 
        for(int i=1; i<=k; i++){
            for(int j=1; j<=k; j++){
                dp[i][j] = INF;
            }
        }
        
        cout<<cal(1, k)<<'\n';
    }
    return 0;
}

##

d[i][j] : ch[i] ~ ch[j] 까지 합칠 때 최소 cost 저장.

어렵다... 많이 많이 복습하자

https://js1jj2sk3.tistory.com/3 참고!!

https://kyunstudio.tistory.com/75 참고

https://www.crocus.co.kr/1073 참고

https://boogalle91-cs.tistory.com/32

11066 파일 합치기[DP]

왜 ch[x] + ... ch[y]까지를 더하는지 이해가 안돼서 자료 찾아보는 중..

 

코드2에 대해서 어떻게 동작하는지 보기 위해 추적한 노트.

dp[1][4]는 두 개씩 묶여서 최소 cost가 되도록 ch[1]~ch[4]까지 합한 cost.