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

문제링크 : https://www.acmicpc.net/problem/11052

11052번: 카드 구매하기

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 987654321;

int arr[1001];
int dp[1001];

int main()
{
    ios_base::sync_with_stdio(0); 
	cin.tie(0);

    int N;
    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];


    return 0;
}

DP문제이다.

카드 1장 : (1)
카드 2장 : (1 + 1) or (2)
카드 3장 : (1 + 2) or (2 + 1) or (3)
카드 4장 : (1 + 3) or (2 + 2) or (3 + 1) or (4)

위와 같이 각 카드에 대해 가능한 가짓수를 찾아서 해당 가짓수에 대한 최대값을 저장해준다.