[C++] BOJ 11066 파일 합치기

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

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>  
#include <climits>

using namespace std;

int main() {
    int t;
    cin >> t; 
    int n;

    for (int i = 0; i < t; i++) {
        vector<int> map;
        int dp[501][501];
        memset(dp, 0, sizeof(dp));
        cin >> n;
        int temp;
        map.push_back(0);
        for (int j = 1; j <= n; j++) {
            cin >> temp;
            map.push_back(map[j - 1] + temp);
        }
        for (int len = 2; len <= n; len++) {
            for (int st = 1; st <= n + 1 - len; st++) {
                int end = st + len - 1;
                dp[st][end] =INT_MAX;
                for (int k = st; k < end; k++) {
                    dp[st][end] = min(dp[st][end], dp[st][k] + dp[k + 1][end] + map[end] - map[st - 1]);
                }
            }
        }
        cout << dp[1][n] << endl;
    }

    return 0;
}

 

Dynamic Programming 문제이다.

dp 테이블을 정의하여 문제를 풀었는데, 

dp[시작 인덱스][끝 인덱스]를 구간을 분할할 때의 비용의 최솟값으로 정의하였다. 즉, 구간을 병합할 때 발생하는 비용의 최소와 현재 구간 합치기 비용을 더한 값이다. 

 

삼중 for문을 사용하여, 

구간의 길이, 시작점, 중간에 분할되는 지점으로 index를 설정했다.

 

또한 C++에서 climits 헤더를 통해 INT_MAX의 값을 편리하게 사용할 수 있었다. INT_MAX란 INT 범위에서 나타낼 수 있는 제일 큰 값을 의미한다. ( 2147483647 )

 

dfadsf