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

 

 

다이나믹 프로그래밍 문제입니다.

 

N개의 카드를 살때 최대한 비싸게 사는 가격을 구하는 문제입니다.

각각 카드 n개마다의 가격이 따로 책정이 되어있습니다.

 

 n개일때 가격 

 n-1개일때 가격 + 1개일때 가격

 n-2개일때 가격 + 2개일때 가격

 n-3개일때 가격 + 3개일때 가격

                 .....

 n-m개일때 가격 + m개일때 가격

 

n개를 구할때 다음과 같은 경우의 수가 있습니다.

경우의 수 중 가장 값이 큰것을 DP에 저장합니다.

 

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

int maxNum = -987654321;
int num[10010];
int memo[10010];

void init()
{
   for (int i = 0; i < 10010; ++i) {
      num[i] = 0;
      memo[i] = 0;
   }
}

int main(int argc, char *argv[])
{
   init();
   int n;
   cin >> n;
   for (int i = 1; i <= n; ++i) {
      cin >> num[i];
      memo[i] = num[i];
   }
   memo[0] = num[0];
   for (int i = 2; i <= n; ++i) {
      for (int j = 1; j < i; ++j) {
         memo[i] = max(memo[i], memo[i - j] + memo[j]);
      }
   }
   for (int i = 1; i <= n; ++i) {
      maxNum = max(maxNum, memo[i]);
   }
   cout << maxNum;
   return 0;
}