[BOJ] 11052번 카드 구매하기

문제 바로가기

접근

아직도 DP를 어떻게 풀지 잘 모르겠다. 처음에 했던 접근은, 배열 dp의 i번째를 '카드 i번까지 보았을 때 카드 N개를 사기 위해 지불하는 최대 금액'으로 두었다. 그러니 카드 i번을 넣기 위해 dp[N-i]에서 새로운 i번째 카드팩의 금액을 넣는 대신 이전 카드팩의 금액을 빼주어야 한다. 하지만 이렇게 풀면 몇 번 카드팩의 금액을 빼야 하는지 알기 어렵다.
그래서 두 번째 접근은 배열 dp의 i번째를 'i개의 카드를 구매하기 위해 지불하는 최대 금액'으로 두는 것이었다. i-1번째까지는 카드 i-1개를 사는 최대 금액을 구했놓았다고 가정하면, i번째에서는 카드 j(1<=j<=i)번을 차례로 넣어 보면서 최대 금액을 구할 수 있게 된다.

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

int main() {
  std::ios::sync_with_stdio(false);
  int N;
  int cards[1001] = {0,};
  int dp[1001] = {0,};
  cin >> N;
  for(int i = 1; i <= N; i++)
    cin >> cards[i];

  dp[1] = cards[1];
  for(int i = 2; i <= N; i++) {
    for(int j = 1; j <= i; j++) {
      dp[i] = max(dp[i], dp[i - j] + cards[j]);
    }
  }
  cout << dp[N];
}