[BOJ/python] 11052: 카드 구매하기

문제

✔️ silver 1

문제 흐름

memo[i]를 i개의 카드를 모을 때 가장 최대 금액으로 정의했을 때,
0 ~ i-1의 memo를 가지고 memo[i]를 구할 수 있다.

i개의 카드를 모을 때 경우의 수는 다음과 같다.

• i개 카드팩 금액
• 1개 카드팩 금액 + (i-1)개 카드를 모으는 최대 금액
• 2개 카드를 모으는 최대 금액 + (i-2)개 카드를 모으는 최대 금액
• ...
• i가 홀수인 경우:
  (i//2)개 카드를 모으는 최대 금액 + (i//2+1)개 카드를 모으는 최대 금액
• i가 짝수인 경우:
  (i//2)개 카드를 모으는 최대 금액 * 2

1~10까지의 합을 빠르게 구하는 방법과 비슷하다.
양 끝부터 짝을 지어 더해주는거다.
그중 가장 큰 값으로 memo를 지정해주면 된다.

처음부터 memo를 cp와 같도록 설정했는데, 카드 수를 맞추기 위해 맨 앞에 0을 추가했다.
모든 카드팩에 대해서 순회하며 다시 그앞의 경우의 수를 순회하므로 O(n^2)의 시간복잡도를 갖는다.

코드

# 카드 구매하기
# dp

import sys
input = sys.stdin.readline

def dp(cp, n):
    # memo[i]: i개의 카드를 모을 때 가장 최대 소비
    memo = [0] + cp

    for i in range(2, n + 1):
        max_value = memo[i]
        for j in range(0, i // 2 + 1):
            if max_value < memo[j] + memo[i-j]:
                max_value = memo[j] + memo[i-j]
                # print(f"changed: memo[{i}] = {memo[j]} + {memo[i-j]} = {max_value}")
        memo[i] = max_value

    # print(*memo)
    return memo[-1]


if __name__ == "__main__":
    n = int(input())
    card_pack = list(map(int, input().split()))

    result = dp(card_pack, n)
    print(result)