카드 구매하기

• 느낀 것
  : 재귀를 통한 완전탐색풀이밖에 떠오르지 않아서 결국 힌트를 참조

코드

#include <cstdio>
#include <vector>
#include <queue>
#include <iostream>
#include <cmath>
using namespace std;
int N;
int arr[10001];
int dp[10001];
int ans=0;
vector<int> ch;
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> N;
    for(int i=0;i<N;i++)
        cin >> arr[i+1];
    dp[1] = arr[1];
    for(int i=2;i<=N;i++)
    {
        dp[i] = arr[i];
        for(int j=1;j<i;j++)
            dp[i] = max(dp[i], dp[j] + arr[i-j]);
    }
    cout << dp[N];
}

• 풀이
  : DP를 이용한 풀이를 해야한다
  (DP[i] = i개의 카드를 뽑는데 필요한 최대 비용)