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

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

11052번: 카드 구매하기

---

SOLUTION

전에 올린 동전 2 문제와 비슷한 방식으로 풀면 된다. 비슷하지만 약간 다른 문제라 살짝만 고치면 풀 수 있다.

동전 2 문제 풀이

---

코드

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

int price[1001];
int dp[1001];

int main() {
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> price[i];
		dp[i] = -1;
	}
	for (int i = 1; i <= n; i++) {
		for (int j = i; j <= n; j++) {
			dp[j] = max(dp[j], dp[j - i] + price[i]);
		}
	}
	cout << dp[n];
}