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

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

11052번: 카드 구매하기

---

//C++

#include <bits/stdc++.h>
#define F_I ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define pi 3.1415926535
using namespace std;
typedef long long ll;

int p[1001];
int d[1001];

int main()
{
	F_I;
	int n;
	int ans;
	cin >> n;
	for (int i = 1; i <= n; i++)
		cin >> p[i];
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= i; j++)
		{
			d[i] = max(d[i - j] + p[j], d[i]);
		}
	}

	cout << d[n] << '\n';
}

 

> d[n] : n개의 카드를 구매하기 위한 최댓값

> d[n] = d[n-i]+p[i]