문제 : 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;
}