[백준/BOJ] 백준 11052번 : 카드 구매하기

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

11052번: 카드 구매하기

n개의 카드를 구매하기 위해 고르는 카드팩의 경우들을 고려하여 지불하는 금액의 최댓값을 구한다

 

코드

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

int cache[1001];
vector<int> card(1001);

int Solve(int n)
{
	//기저사례
	if (n == 0)
		return 0;

	int& ret = cache[n];

	//계산한적이 있을때
	if (ret != -1)
		return ret;

	for (int i = 1; i <= card.size(); i++)
	{
		if (i <= n)
			ret = max(ret, Solve(n - i) + card[i]);
	}

	return ret;
}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	memset(cache, -1, sizeof(cache));

	int n;
	int temp;

	cin >> n;

	for (int i = 1; i <= n; i++)
	{
		cin >> temp;
		card[i] = temp;
	}

	cout << Solve(n);

	return 0;
}