[C++]BOJ 11052 - 카드 구매하기

좀 생각 많이 한 문제다.
카드 n개를 구매할 때 최대 금액은 카드 n - j개를 구매할 때의 최대 금액 + 카드 j개가 담겨있는 카드팩의 가격일 것이다.
카드팩의 가격은 arr[]에 저장하고 카드 n개를 가장 비싸게 구매할 때 금액을 dp[n]에 저장한다면, 카드 n개를 가장 비싸게 구매할 때 금액은 dp[n], dp[n - 1] + arr[1], dp[n - 2] + arr[2], dp[n - 3] + arr[3]…dp[n - n] + arr[n] 중 가장 큰 값이 된다.

#include <iostream>
#include <algorithm>
using namespace std;
int n, arr[1001], dp[1001];
int main() {
	cin >> n;
	for(int i = 1; i <= n; i++)
		cin >> arr[i];
	for(int i = 1; i <= n; i++)
		for(int j = 1; j <= i; j++)
			dp[i] = max(dp[i], dp[i - j] + arr[j]);
	cout << dp[n];
}