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

11052번: 카드 구매하기

#include <iostream>
using namespace std;

auto main()->int {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr); cout.tie(nullptr);
	int n; cin >> n;
	int* P = new int[(n + 1)]();
	int* d = new int[(n + 1)]();
	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] = std::max(d[i], d[i - j] + P[j]);
		}
	}

	cout << d[n] << endl;

	delete[] d;
	delete[] P;
}