[백준 11052] 카드 구매하기 (DP) (C/C++)

#include <iostream>
#include <algorithm>
using namespace std;
 
int N;
long long card[1010];
long long dp[1010];
 
long long solve(int cnt)
{
    if(dp[cnt] != 0)
    {
        return dp[cnt];
    }
 
    for(int i = 1; i <= N; i++)
    {
        if(cnt+i <= N)
        {
            dp[cnt] = max(dp[cnt], solve(cnt+i) + card[i]);    
        }
    }
    
    return dp[cnt];
}
 
int main(void)
{
//    freopen("B11052_input.txt", "r", stdin);
    
    cin >> N;
    
    for(int i = 1; i <= N; i++)
    {
        cin >> card[i];
    }
    
    cout << solve(0);
    
    return 0;
}