11052 c++ - 카드 구매하기

DP문제입니다. 헷갈리는 흐름을 정리하기 위해서 글을 씁니다.

dp[i - j]는 문제를 이해하는 데 매우 중요한 부분입니다. 이 부분을 명확히 이해하는 것이 문제 해결의 핵심입니다.

dp[i - j]가 의미하는 것

dp[i]는 i개의 카드를 구매할 때 지불할 수 있는 최대 금액입니다. 그렇다면, dp[i - j]는 i - j개의 카드를 구매할 때 지불할 수 있는 최대 금액을 의미합니다.

다시 말해서, 이미 i - j개의 카드를 최대로 구매한 상태에서 j개의 카드가 들어있는 카드팩을 추가로 구매했을 때의 최댓값을 계산하는 것입니다.

구체적인 예시로 살펴봅시다:

• 만약 i = 4, 즉 4개의 카드를 구매하려고 한다면, 우리는 다음과 같이 생각할 수 있습니다:
  • j = 1일 경우:
    • dp[4 - 1] = dp[3]: 이미 3개의 카드를 구매한 최댓값에다가, 1개의 카드팩을 추가로 구매합니다.
  • j = 2일 경우:
    • dp[4 - 2] = dp[2]: 이미 2개의 카드를 구매한 최댓값에다가, 2개의 카드팩을 추가로 구매합니다.
  • j = 3일 경우:
    • dp[4 - 3] = dp[1]: 이미 1개의 카드를 구매한 최댓값에다가, 3개의 카드팩을 추가로 구매합니다.
  • j = 4일 경우:
    • dp[4 - 4] = dp[0]: 0개의 카드를 구매한 상태에서, 4개의 카드팩을 한 번에 구매합니다.

즉, dp[i - j] + price[j]는 **"i - j개의 카드를 최대로 구매한 후에 j개의 카드팩을 구매한 경우"**의 값을 계산하는 것이며, 그 중에서 최대값을 찾는 과정입니다.

전체 흐름을 다시 정리하면:

1. dp[i]는 i개의 카드를 구매할 때의 최댓값을 저장합니다.
2. 각 카드팩을 한 번씩 고려하면서, 그 카드팩을 사기 전의 상태(i - j개의 카드)에 추가로 j개 카드팩을 구매하는 방법을 시도합니다.
3. 최댓값을 갱신합니다.

이 방식으로 dp[i]에 i개의 카드를 구매하는 최댓값을 저장하게 됩니다.

구체적인 예제:

만약 n = 4이고 카드팩 가격이 price = [0, 1, 5, 6, 7]일 때, DP 배열은 다음과 같이 업데이트됩니다:

• i = 1일 때:
  • dp[1] = max(dp[1], dp[1-1] + price[1]) = max(0, 0 + 1) = 1
• i = 2일 때:
  • dp[2] = max(dp[2], dp[2-1] + price[1]) = max(0, 1 + 1) = 2
  • dp[2] = max(dp[2], dp[2-2] + price[2]) = max(2, 0 + 5) = 5
• i = 3일 때:
  • dp[3] = max(dp[3], dp[3-1] + price[1]) = max(0, 5 + 1) = 6
  • dp[3] = max(dp[3], dp[3-2] + price[2]) = max(6, 1 + 5) = 6
  • dp[3] = max(dp[3], dp[3-3] + price[3]) = max(6, 0 + 6) = 6
• i = 4일 때:
  • dp[4] = max(dp[4], dp[4-1] + price[1]) = max(0, 6 + 1) = 7
  • dp[4] = max(dp[4], dp[4-2] + price[2]) = max(7, 5 + 5) = 10
  • dp[4] = max(dp[4], dp[4-3] + price[3]) = max(10, 1 + 6) = 10
  • dp[4] = max(dp[4], dp[4-4] + price[4]) = max(10, 0 + 7) = 10

최종적으로 dp[4] = 10이므로 답은 10이 됩니다.

이 과정을 통해 dp[i - j]가 어떻게 각 단계에서 사용되는지 명확하게 이해할 수 있습니다.

#include <iostream>
#include <vector>

using namespace std;

int main() {
  int n;
  cin >> n;
  vector<int> price(n + 1);
  vector<int> dp(n + 1, 0);

  for (int i = 1; i <= n; i++) {
    cin >> price[i];
  }

  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= i; j++) {
      dp[i] = max(dp[i], dp[i - j] + price[j]);
    }
  }

  cout << dp[n];
  return 0;
}