[BOJ]11052_카드구매하기

📃 카드 구매하기

import sys
input = sys.stdin.readline 

n = int(input())
p = [0]+list(map(int, input().split()))
# max_prices = p 하면, 복사가 아니라 참조가 되어
# 한 곳을 변경하면 다른 곳도 똑같이 변경된다.
# (이 코드에서는 참조로 해도 이상은 없음.)
max_prices = p[:]

for i in range(2, n + 1):
    for j in range(1, i // 2 + 1):
        if max_prices[i] < max_prices[i - j] + max_prices[j]:
            max_prices[i] = max_prices[i - j] + max_prices[j]

print(max_prices[n])

풀이

동적 프로그래밍 문제를 풀 때는 우선 기본 점화 관계를 밝힌 뒤에, 보다 효율성을 높일 수 있는 방안을 생각하도록 해야겠다.

카드 n장을 한번에 구매하는 가격이 price(n)이고,
카드 n장을 구매할 때의 최대 금액을 max_price(n)이라고 하자.

그렇다면 max_price(n)은

price(n)
max_price(n - 1) + max_price(1)
max_price(n - 2) + max_price(2)
...
max_price(n - k) + max_price(k) 중 가장 큰 값과 같다.