[boj] 백준 11052 카드 구매하기 (c++) - dp

[문제]

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

11052번: 카드 구매하기

 

[풀이]

카드팩의 가격에 따라 최댓값이 달라진다. 

예를 들어 4개의 카드만큼을 구매하고자 한다면, 4개가 들어있는 카드팩, 3개가 들어있는 카드팩+1개가 들어있는 카드백, 2개가 들어있는 카드팩*2, 이런 식으로 구매가 가능하다.

즉 N개의 카드 구매에 대해 N-a개의 카드를 구매 + a개의 카드를 구매하는 가능성들을 비교하여 최대 비용을 구하면 된다.

따라서 점화식은 dp[N] = max(dp[N], dp[N-a]+dp[a])  이다.

 

[코드]

 

#include <iostream>
#include <algorithm>
#include <map>
#include <string>
#include <queue>
#include <cstring>

using namespace std;

int N;
int dp[1001];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    // N개의 카드를 구매하기 위해 민규가 지불해야 하는 금액의 최댓값 - dp
    cin >> N;

    dp[0] = 0;
    for(int i=1; i<=N; i++){
        cin >> dp[i];
    }

    for(int i=2; i<=N; i++){
        for(int j=1; j<=i/2; j++){
            dp[i] = max(dp[i], dp[i-j]+dp[j]);
        }
    }

    cout << dp[N];

}