11066 파일 합치기

문제 링크(www.acmicpc.net/problem/11066)](www.acmicpc.net/problem/11066)

 

 

 

내 코드(https://github.com/haung921209/TIL/blob/master/Documents/PS/DP/11066.md)

1. 첫번째 풀이 - 참조 후 푼 문제.

코드

#pragma warning(disable:4996)
#include<iostream>
#include<vector>
#include<math.h>
#include<algorithm>
#include <random>
#include<time.h>
#include<string>
#include<queue>
#include <set>
#include <map>
#include <list>
#include<stack>
#include<deque>
#include<cstring>
#define ll  long long
#define INF 987654321
using namespace std;
vector<vector<int>> dp;
vector<int> saveSum;

int pSum(int start, int end) {
    if (start == 0)
        return saveSum[end];
    else
        return saveSum[end] - saveSum[start - 1];
}

int calDp(int start, int end) {

    int& ret = dp[start][end];

    if (dp[start][end] != -1)return dp[start][end];


    ret = INF;

    for (int idx = start; idx < end; idx++) {
        int partialSum = pSum(start, end);
        int left = calDp(start, idx);
        int right = calDp(idx + 1, end);
        ret = min(ret, left + right + partialSum);
    }
    dp[start][end] = ret;
    return dp[start][end];
}

void solve(int num) {
    int ret = INF;

    for (int i = 0; i < num - 1; i++) {
        ret = min(ret, calDp(0, i) + calDp(i + 1, num - 1));
    }

    cout << ret << endl;
}


int main() {

    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    int t; cin >> t;
    while (t > 0) {
        int k;
        cin >> k;
        vector<int> inp(k);
        dp = vector<vector<int>>(k, vector<int>(k, -1));


        for (int i = 0; i < k; i++) {
            cin >> inp[i];
            dp[i][i] = inp[i];
        }
        saveSum = vector<int>(k, 0);
        saveSum[0] = inp[0];
        for (int i = 1; i < k; i++) {
            saveSum[i] = saveSum[i - 1] + inp[i];
        }
        solve(k);

        --t;
    }

    return 0;
}

• 위 코드에서 dp는 최종 값을 저장하는 것이 아니다. 최종적으로 값을 계산할 때, 해당하는 부분문제를 단순히 더할 수 있도록 계산해놓은 값이다. 다시 말해, 계산하는데 들어간 Cost와 다음 단계에서 계산하기 위한 Cost를 합쳐놓은 값이다.
• 최종 단계에서는(dp[begin][start]값을 말함.) 추후 계산하기 위한 단계가 없으므로, 다음 단계를 계산하기 위한 Cost는 필요가 없다. 따라서, 해당 문제처럼 dp를 설계할 시, 단순히 dp[begin][end]를 출력한다면 WA를 달성할 수 있다.

2. 두번째 풀이 - dp의 역할을 변경한 풀이

#pragma warning(disable:4996)
#include<iostream>
#include<vector>
#include<math.h>
#include<algorithm>
#include <random>
#include<time.h>
#include<string>
#include<queue>
#include <set>
#include <map>
#include <list>
#include<stack>
#include<deque>
#include<cstring>
#define ll  long long
#define INF 987654321
using namespace std;
vector<vector<int>> dp;
vector<int> saveSum;

int pSum(int start, int end) {
    if (start == 0)
        return saveSum[end];
    else
        return saveSum[end] - saveSum[start - 1];
}

int calDp(int start, int end) {

    int& ret = dp[start][end];

    if (dp[start][end] != -1) {
        return dp[start][end];
    }

    ret = INF;

    for (int idx = start; idx < end; idx++) {
        int left = calDp(start, idx);
        int right = calDp(idx+1, end);
        int partialSum = pSum(start, end); // left와 right를 합치는데 필요한 비용
        ret = min(ret, left+right+ partialSum);
    }
    dp[start][end] = ret;
    return dp[start][end];
}


int main() {

    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    int t; cin >> t;
    while (t>0) {
        int k;
        cin >> k;
        vector<int> inp(k);
        dp = vector<vector<int>>(k, vector<int>(k,-1));

        for (int i = 0; i < k; i++) {
            cin >> inp[i];
            dp[i][i] = 0; //합치는 cost를 고려해야 하는 방법이므로, start와 end가 같다면 합치는 cost를 고려할 이유가 없으므로 0 저장
        }
        saveSum = vector<int>(k, 0);
        saveSum[0] = inp[0];
        for (int i = 1; i < k; i++) {
            saveSum[i] = saveSum[i - 1] + inp[i];
        }
        cout << calDp(0, k-1) << endl;

        --t;
    }

    return 0;
}

• 여기서의 dp[start][end]는 결과값을 계산하기 위한 부분문제의 Cost 총합을 저장해놓은 것이 아니라, 그 자체로 결과값이 된다. 따라서, dp[idx][idx]의 경우, 이미 idx 위치에 해당하는 부분은 계산할 필요가 없으므로, 0이 된다.
• 별도로 계산하는 단계(solve)가 없는 것이 내가 생각하는 방식과 맞다고 생각.
• 다만, 문제에 따라 한 방향으로 풀어야 하는 경우가 있을 수 있으므로, 둘 다 생각해 볼 필요 있음.