[C++] 백준 - 11052 : 카드 구매하기

문제 링크

11052번: 카드 구매하기

 

풀이 ) DP

  초기화를 할 때 입력되는 카드로 바로 초기화를 한 후 이후

  n개의 카드를 n-m개, m개의 카드 두 부분으로 나누어서 n-m의 카드로 이루어진 최댓값에 m개가 포함된 카드팩의 합의 최대를 구한다.

 

#include <cstdio>
#include <algorithm>
using namespace std;

int main(void)
{
    int n, card[1001], memo[1001] = {0, };
    scanf("%d", &n);
    for(int i = 1; i <= n; ++i){
        scanf("%d", card+i);
        memo[i] = card[i];
    }
    for(int i = 2; i <= n; ++i)
        for(int j = 1; j <= i; ++j)
            memo[i] = max(memo[i], memo[i-j]+card[j]);
    printf("%d\n", memo[n]);
    return 0;
}