[백준] 11052번 카드 구매하기 - Python

이번에 해결해 볼 문제는 백준에 있는 11052번 카드 구매하기입니다.

---

문제 설명

1. 8가지 종류의 카드가 있을 때 카드는 카드팩의 형태로만 구매할 수 있고, 카드팩의 종류는 카드 1개가 포함된 카드팩, 카드 2개가 포함된 카드팩, … 카드 N개가 포함된 카드팩과 같이 총 N가지가 존재합니다.
2. 민규는 카드의 개수가 적은 팩이더라도 가격이 비싼 카드팩을 사고자 합니다.
3. 민규가 구매하려는 카드가 N개이고 카드가 i개 포함된 카드팩의 가격을 $P_i$원이라고 할 때 민규가 지불해야하는 금액의 최댓값은 얼마인지 구하면 됩니다.

문제 해결 아이디어

• N을 만들 수 있는 합의 조합을 생각하면 됩니다.
  • 즉, $N = a + b$의 형태로 생각할 수 있는데 여기서 $P_a, P_b$가 큰 것을 구하면 됩니다.
• 여기서 놓칠 수 있는 부분이 있습니다.
  • 그냥 $N = a + b$라고 생각하여 해당 결과들만 비교하면 안됩니다.
  • 예를 들어 카드 4개를 구매하기 위해서는 $4 = 2 + 2$가 있을 수 있는데 2개를 사는데 있어서 금액의 최대값은 카드 2개가 들어있는 카드팩일 수 있지만 카드 1개가 들어있는 카드팩 2개를 사는 것일 수 있습니다.
  • 따라서 1개부터 ~ N개까지 각각의 금액 최댓값을 구해나가야 합니다.
• 해당 문제를 풀기 위한 알고리즘은 Dynamic Programming인데 이를 알 수 있는 몇 가지 이유들이 존재합니다.
  • N과 $P_i$의 범위가 매우 작습니다.
  • 규칙성이 존재합니다. ($N = a + b, max(\text{max_value}, P_a+P_b)$)
  • 하나씩 해결해 나가야 합니다.

문제 해결 코드

import sys

input = sys.stdin.readline

N = int(input())

table = [0] + list(map(int, input().split()))

for i in range(1, N + 1):
    for j in range(i):
        table[i] = max(table[i], table[j] + table[i - j])
print(table[N])