[백준/Python3] 11052 카드 구매하기

https://www.acmicpc.net/problem/11052

---

풀이

dynamic programming을 이용해 해결하는 문제다.

n장의 카드를 구해하기 위해 지불해야 할 최댓값을 구하는 문제며, 점화식은
dp[n] = max(P[n], dp[1] + P[n-1], dp[2] + P[n-2], ... , dp[n-1] + P[1])로 나타낼 수 있다. 이를 코드로 구현해 해결한다.

코드

# Initial
N = int(input())
P = list(map(int, input().split()))
P.insert(0, 0) # 인덱스 맞추기용
dp = [0 for _ in range(N+1)]
answer = 0

# P[n] = 카드 n개가 포함된 카드팩의 가격

# Make DP table
dp[1] = P[1]
for i in range(1, N+1):
    temp = 0
    for j in range(1, i):
        temp = max(temp, dp[i-j] + P[j])
    dp[i] = max(temp, P[i])

# Answer
answer = dp[N]
print(answer)