[C++] 백준 11052 [카드 구매하기]

문제설명

카드팩 N개가 주어지고, 첫 번째 카드팩에는 1개의 카드가, 두 번째 카드팩에는 2개의 카드가, N 번째 카트팩에는 N개의 카드가 있다.
또한, 각 카드팩의 가격이 주어진다.
민규는 총 N개의 카드를 구매하려고 하는데, 이 때 지불해야하는 금액의 최대값을 출력하는 문제이다.

풀이방법

Top-down 풀이방식이다.
Cache array는 이중 배열로 구현하였다.
vector<int> card : 카드팩의 가격
DP(a, b)의 정의 : b까지의 카드팩에서 a개의 카드를 구매할 때 지불해야하는 금액의 최대값
문제의 정답은 DP(N,N)이 된다.
기저조건은 a 또는 b가 0인 경우이다.

만약, a보다 b가 큰 경우에는 카드팩을 선택할 수 없으므로, b-1 번째 카드팩까지 선택하는 것과 같다.(DP(a, b-1))
그 외의 경우, 현재 카드팩을 선택한 경우와 아닌경우 2가지로 나눌 수 있다.

1) 선택한 경우
구매해야 하는 카드의 수가 b만큼 줄어든다(b번째 카드팩에는 b개의 카드가 들어있다)
그리고 금액은 card[b]만큼 늘어난다.
그 후, 더 이상 b번째 카드팩을 선택 안하는 경우와, 선택할 수도 있는 2가지 경우가 생긴다.
1-1) 더 이상 b번째 카드팩을 선택하지 않는 경우
DP(a-b, b-1) + card[b]
1-2) b번째 카드 팩을 선택할 수도 있는 경우
DP(a-b, b) + card[b]

2) 선택하지 않은 경우
DP(a,b-1)

1-1, 1-2, 2 총 3가지의 경우 중 최대값이 DP(a,b)이다.

점화식

\(DP(a, b) = DP(a, b-1)\) (a < b 인 경우) \(DP(a, b) = max(DP(a, b-1), DP(a-b, b) + card[b], DP(a-b, b-1) + card[b])\)

위 점화식에 따라 코드를 작성하면 아래와 같다.

소스코드

#include<iostream>
#include<vector>
#include<cstring>

using namespace std;

int N;
vector<int> card;
int cache[1001][1001];

int DP(int a, int b){
    if(a == 0) return 0;
    if(b == 0) return 0;
    
    int& ret = cache[a][b];
    if(ret != -1) return ret;

    if(a<b) return ret = DP(a,b-1);
    ret = max(max(DP(a-b, b) + card[b-1], DP(a,b-1)), DP(a-b, b-1) + card[b-1]);
    return ret;
}

int main(){
    cin >> N;
    memset(cache, -1, sizeof(cache));
    for(int i=0; i<N; i++){
        int n;
        cin >> n;
        card.push_back(n);
    }
    cout << DP(N, N);
}