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

https://www.acmicpc.net/problem/11052

11052번: 카드 구매하기

dp[n]은 n개를 구입 할 때 최대 금액으로 정하고 n=1 은 p[1]로 초기화한다
그리고 n=2부터 dp[n] = dp[n-i] + dp[i] 의 점화식을 이용해 풀면 된다

#include <bits/stdc++.h>

using namespace std;
int n;
int p[1001], dp[1001];

int main(void) {
    cin >> n ;

    for(int i=1; i<=n; i++){
        cin >> p[i];
    }

    dp[1] = p[1];
    for(int i=2; i<=n; i++){
        int maxnum = p[i];
        for(int j=1; j<=i-1; j++){
            maxnum = max(maxnum, dp[j] + dp[i-j]);
        }
        dp[i] = maxnum;
    }
    cout << dp[n] << endl;

    return 0;
}

반응형