백준 11066번: 파일 합치기

백준 11066번: 파일 합치기

11066번: 파일 합치기

DP문제지만 정말 어려웠다. 문제를 오해하면 안되는게 소설이다보니까 페이지가 섞이면 안된다. 이거 모르면 평생 못풀 문제다. 그리고 각 파일을 합치는 과정을 구하기가 너무 어려웠다. 적절한 비용을 구하기 위해서 2차원 배열의 dp를 이용했고 dp[시작번호][끝번호]를 사용해서 dp는 시작번호부터 끝번호까지의 비용을 담게된다.

코드에 주석을 달아놨다.

 

#include<iostream>
#include<algorithm>
using namespace std;

// DP 초기화를 위한 최대값
#define INF 0xFFFFFFF;

int solution(int novel[], int k){
    int answer = 0;
    long dp[501][501];
    long psum[501];

    // 1부터 i번째까지의 합을 나타낸다.
    for(int i = 1; i <= k; i++){
        psum[i] = psum[i-1] + novel[i];
    }

    // i는 시작번호
    for(int i = 1; i <= k; i++){
        // r은 i 부터 i + r번째 값을 구할때 더하는 인덱스 값입니다.
        for(int r = 1; i+r <= k; r++){
            int e = i+r;
            dp[r][e] = INF;
            //dp[1][4]를 구한다 할때
            //dp[1][1]+dp[2][3], dp[1][2]+dp[3][4], dp[1][3]+dp[4][4] 를 구하는 과정이다.
            //psum을 사용하는 이유는 여기서 구하는 것은 값의 합이 아닌
            //소요되는 비용을 구하는 것이기 때문이다.
            //dp[1][2]가 70 dp[3][4]가 80이면
            //dp[1][4]가 150이 아닌 dp[1][2]+dp[3][4]+[1]부터[4]까지의합 = 300이 되어야한다.
            for(int k = r; k < e; k++){
                dp[r][e] = min(dp[r][e],\
                    dp[r][k] + dp[k+1][e] + psum[e] - psum[r-1]);
            }
        }
    }

    //정답은 1부터 k까지의 합의 최솟값
    answer = dp[1][k];
    return answer;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int test_case;
    int novel[501];
    int k;
    cin >> test_case;
    while(test_case--){
        cin >> k;
        for(int i = 1; i <= k; i++){
            cin >> novel[i];
        }
        cout << solution(novel, k) << "\n";
    }

    return 0;
}