BOJ11052: 카드 구매하기

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

}