알고리즘 :: 백준 :: DP :: 11052 :: 카드 구매하기

문제

민규가 구매하려고 하는 카드의 개수 N과 카드 팩의 가격이 주어졌을 때, N개의 카드를 구매하기 위해 민규가 지불해야 하는 금액의 최댓값을 구하는 프로그램을 작성하시오

문제접근

1. N개의 카드를 구매하기 위해 지불해야하는 금액의 최댓값을 구하는 문제이므로 전형적인 DP 문제임을 알 수 있다.
2. 솔직히 인정하자. Greedy로 푸는 것이 가장 좋다고 생각했다면 당장 그 생각을 그만두자. 동전 반환 문제처럼 치명적인 반례가 존재한다. Greedy가 최적해를 내기 위해서는 두 가지 조건이 성립해야하는데, 이 문제는 부분해의 최적해가 전체의 최적해임을 장담할 수 없다.
3. 카드 팩을 몇 개 선택하던지 간에 내부 카드들의 합은 N이다. 즉 점화식은 다음과 같이 나온다. $D(n) = D(n-i)+P[i]$ (N개 고를 때 최대값은 N-i개 고를 때 최대값에 카드가 i개 든 카드팩의 가격)

코드

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

static int N = 0;
static vector<int> dp(1001, 0);

int solve(const vector<int>& card) {
    for (int i = 1; i <= N; ++i)
        for (int j = 1; j <= i; ++j)
            dp[i] = max(dp[i], dp[i - j] + card[j]);
    return dp[N];
}

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    cin >> N;
    vector<int> card(N + 1);
    for (int i = 1; i <= N; ++i) cin >> card[i];

    cout << solve(card) << '\n';
}

결과