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

11052번: 카드 구매하기

전형적인 dp 문제이다. 배낭 문제와 같은 맥락으로 쉽게 풀 수 있다. 간단하게 풀 수 있었다.

`#include <iostream>
#include <algorithm>

using namespace std;

int N;
int P[1001];
int dp[1001];

void solution() {
    for (int i = 2; i <= N; i++) {
        for (int j = 1; j < i; j++) {
            dp[i] = max(dp[i], dp[i - j] + P[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; i++) {
        cin >> P[i];
        dp[i] = P[i];
    }

    solution();

    return 0;
}