[백준] 11066: 파일 합치기

0. 문제 주소

 

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

11066번: 파일 합치기

 

 

1. 풀이

 

 

[PS/DP] - [BOJ] 11049: 행렬 곱셈 순서와 똑같은 기법을 사용하는 dp 문제.

 

마찬가지로 구간을 두 개로 나누어서 이전에 저장해뒀던 'i번째 파일부터 j번째 파일까지 합치는데 드는 최소 비용'을 이용하여 테이블을 갱신한다.

 

2차원 dp 테이블에서 대각 성분, 즉 i == j일 때는 파일 하나를 합치는 데 드는 비용을 의미하므로 0으로, 

i == j-1일 때는 파일 두개를 합치는 데 드는 최소 비용을 의미하므로 두 파일 크기의 합으로 미리 초기화해준다.

 

다음 파일 개수가 3개 이상일 때는, 맨 마지막에 모든 파일 크기를 더해주어야 하기 때문에, 부분합 배열도 따로 만들어 주어 테이블 갱신에 활용한다.

 

테이블 갱신 코드는 다음과 같다.

 

for (int i=1;i<=N-1;i++){
    dp[i][i+1] = file[i] + file[i+1];
}

for (int d=2;d<=N-1;d++){
    for (int i=1;i<=N-d;i++){
        int j = i+d;
        int curr_min = INF;
        for (int k=i;k<j;k++){
            curr_min = min(curr_min, dp[i][k] + dp[k+1][j]);
        }
        dp[i][j] = curr_min + psum[j] - psum[i-1];
    }
}

 

 

2. 풀이 코드

 

* 유의할 점

 

1. i == j-1일 때 dp[i][j-1] 성분 초기화 유의

2. psum 배열 생성

 

#include <bits/stdc++.h>
#define MAX 505
#define INF 987654321

using namespace std;

int T, N;
int file[MAX];
int psum[MAX];
int dp[MAX][MAX];

int main(){
    #ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    #endif // ONLINE_JUDGE

    scanf("%d", &T);
    for (int x=0;x<T;x++){
        memset(dp, 0, sizeof(dp));
        memset(psum, 0, sizeof(psum));

        scanf("%d", &N);
        for (int i=1;i<=N;i++){
            scanf("%d", &file[i]);
        }
        for (int i=1;i<=N;i++){
            psum[i] = psum[i-1] + file[i];
        }

        for (int i=1;i<=N-1;i++){
            dp[i][i+1] = file[i] + file[i+1];
        }

        for (int d=2;d<=N-1;d++){
            for (int i=1;i<=N-d;i++){
                int j = i+d;
                int curr_min = INF;
                for (int k=i;k<j;k++){
                    curr_min = min(curr_min, dp[i][k] + dp[k+1][j]);
                }
                dp[i][j] = curr_min + psum[j] - psum[i-1];
            }
        }

        printf("%d\n", dp[1][N]);
    }
}