문제

11052번: 카드 구매하기

풀이

• 그냥 완전 탐색에 메모이제이션 추가된 느낌
• n 개의 카드팩을 사는데 최대로 드는 비용을 dp에 저장
• 실제로 모든 경우를 다 사보는데 만약에 이미 사본경우가 있으면 저장해둔 값 쓴다.
• 이떄 n 이 음수가 되면 안되기떄문에 if (num - i >= 0) 조건문을 걸어준다.
• 아니면 if (num < 0) return (-999999) 이런식도 가능하다.

구현

#include <iostream>
#include <vector>
#include <set>

using namespace std;

int n;
vector<int> cards;
vector<int> dp;

void pre() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
}

void input() {
	cin >> n;
	cards.resize(n + 1);
	dp.resize(n + 1);
	for(int i = 1; i <= n; i++)
		cin >> cards[i];
}

int rec(int num) {
	int price;

	price = 0;
	if (num == 0)
		return (0);
	if (dp[num])
		return (dp[num]);
	for(int i = 1; i <= n; i++)
		if (num - i >= 0)
			price = max(rec(num - i) + cards[i], price);
	dp[num] = price;
	return (dp[num]);
}

void solve() {
	cout << rec(n) << endl;
}

int main() {
	input();
	solve();
	return (0);
}