[백준 11066][C++] 파일 합치기

문제

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

11066번: 파일 합치기

 

[풀이 참고 링크 1]   [풀이 참고 링크 2]

 

풀이 과정

처음에는 가장 작은 순서대로 정렬해서 가장 작은 것부터 결합하면 되는 것 아닌가라는 착각을 했었지만, 좌 우 정보가 사라지기 때문에 그렇게 처리하면 오답이 나온다. 그렇다면 각각에서 좌 우 탐색을 하며 DP를 진행해야 하는 것인가 고민하였다.

 

해당 문제 시간 안에 풀지 못했다. DP로 구현해야겠다는 생각이 들었지만, 구현에서 어려움을 겪었다. 따라서 찾아본 풀이들 중 하나를 리뷰할 예정이다. (링크 1을 선택했다)

 

 

필자가 고민했던 좌 우 방향의 탐색을 링크 1의 필자는 탐색할 범위를 점점 늘려나가며 DP를 진행하는 방식을 선택했다. 만약 총 15개를 합쳐야 할 때, 1칸을 합치는 경우를 모두 탐색, 2칸을 합치는 경우를 모두 탐색, 3칸을 합치는 경우를 모두 탐색,... 15개를 합치는 경우를 모두 탐색하는 과정을 거쳤다. 이때 각 모든 탐색에서는 다시 두 부분으로 나누어 제일 작은 값을 저장하며 진행하도록 구현했다.

 

예를 들어 5 4 3 5 98 21 14를 연결해야 한다면,

5 / 4 3 5 98 21 14

5 4 / 3 5 98 21 14

5 4 3 / 5 98 21 14

5 4 3 5 / 98 21 14

5 4 3 5 98 / 21 14

5 4 3 5 98 21  /14

 

경우로 나누어 이전의 DP를 이용해 구할 수 있게 된다. (1칸 합치는 경우, 2칸 합치는 경우... 를 순차적으로 진행했으므로)

 

 

소스 코드

#include <iostream>
#include <algorithm>
#define INF 1e9
using namespace std;

int sum[501], file[501], dp[501][501];

int main(){
    int T; cin >> T;
    while(T--){
        int t; cin >> t;
        for(int i=1; i<=t; i++){
            cin >> file[i];
            sum[i] = sum[i-1] + file[i];
        }

        for(int i=1; i<=t; i++){
            for(int j=1; j<=t; j++){
                dp[j][i+j] = INF;
                for(int k=j; k<i+j; k++){
                    dp[j][i+j] = min(dp[j][i+j], dp[j][k] + dp[k+1][i+j] + sum[i+j] - sum[j-1]);
                }
            }


        }
        cout << dp[1][t] << "\n";
    }
    return 0;
}

 

결과 및 후기

아직 DP 문제에 대해 이해가 부족하고 적용이 힘든 것이 느껴진다. 분명 DP는 코드의 길이는 짧지만, 그것을 만족시키기 위해 배열을 만들고 배열의 index를 설정하여 기록을 업데이트하는 섬세한 과정이 아직은 힘들게 느껴진다.

 

문제를 풀지 못하였을 때, 링크 2와 같이 여러 사람들의 풀이를 모아서 분석하는 것도 좋은 공부 방법인 것 같아 남기게 되었다.