문제 : boj 11052

풀이

  • DP 문제
  • 배열 _sum[n]은 n개 카드 구매시 최대값이다.
  • 배열 _sum의 값을 이용해 구매 카드 수가 n개일 때, (n-1장 구매시 최대값 + 1장 구매가격),(n-2장 구매시 최대값 + 2장 구매가격),…,(n장구매가격)을 비교해 최대값을 _sum[n]에 넣는다.

C++

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

int N, price[1001];
unsigned int _sum[1002];

void dp(int n){
    unsigned int _max(0);
    if(n == 1) {
        _sum[1] = price[0];
        dp(n+1);
        return;
    }
    else if(n == N+1) return;
    for (int i(1); i < n; i++){
        unsigned int tmp = _sum[n-i]+_sum[i];
        if(tmp > _max) _max = tmp;
    }
    if (_max < price[n-1]) _max = price[n-1];
    _sum[n] = _max;
    dp(n+1);
}

int main(){
    freopen("input.txt","r", stdin);
    cin >> N;
    for (int i(0); i < N; i++){
        cin >> price[i];
    }
    dp(1);
    cout << _sum[N];
    fclose(stdin);
    return 0;
}