백준 11052 카드 구매하기(dynamic programming)

#include <iostream>
#include <algorithm>
 
using namespace std;
 
int n;
int card[1001];
int dp[1001];
 
void maxPrice()
{
    for (int i = 1; i < n + 1; i++)
    {
        for (int j = 1; j < i + 1; j++)
        {
            dp[i] = max(dp[i], dp[i - j] + card[j]);
        }
    }
    cout << dp[n];
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> n;
    for (int i = 1; i < n + 1; i++)
    {
        int tmp;
        cin >> tmp;
        card[i] = tmp;
    }
    maxPrice();
}

 

n개의 카드를 뽑는 다는 가정을 하는 경우. n-1개의 카드와 1개의 카드, n-2개의 카드와 2개의 카드, n-3개의 카드와 3개의 카드..... 이 모든 경우를 고려해야 된다. 이 때문에 dp[i]=max(dp[i], dp[i-j]+card[j]) 라는 점화식이 나오게 된다.