민규가 구매하려고 하는 카드의 개수 N과 카드 팩의 가격이 주어졌을 때, N개의 카드를 구매하기 위해 민규가 지불해야 하는 금액의 최댓값을 구하는 프로그램을 작성하시오
동전 반환 문제
처럼 치명적인 반례가 존재한다. Greedy가 최적해를 내기 위해서는 두 가지 조건이 성립해야하는데, 이 문제는 부분해의 최적해가 전체의 최적해임을 장담할 수 없다.#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';
}