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

문제

풀이

모든 카드팩의 가격을 비교해 최댓값을 찾아야 한다 == DP이다.

<Example> 

n = 5
p = [1,4,2,7,3]


DP[A] = B 
A장의 카드를 사는데 지불해야하는 최대 금액이 B원이다.


카드 1장 사는데 지불해야하는 최대 금액은 1원 
DP[1] = max(P[1]) = 1

카드 2장 사는데 지불해야하는 최대 금액은 4원 
DP[2]  = max(P[2] , P[1] * 2)  = 4 

      = max(2장 들어있는 카드팩 하나 사는 금액, 1장 카드팩 사는 금액 + 1장 카드 사는 최대 금액)
      = max(P[2], DP[1]+P[1])


카드 3장 사는데 지불해야하는 최대 금액은 
DP[3] = max(P[3], P[2]*1 + P[1], P[1]*3) = 5원 

     = max(3장 들어있는 카드팩 하나 사는 금액,\ 
           2장 들어있는 카드팩 하나 사는 금액 + 1장 카드 사는 최대 금액,
           1장 들어있는 카드팩 하나 사는 금액 + 2장 카드 사는 최대 금액)

     = max(P[3], P[2]+DP[1], P[1]+DP[2])


카드 4장 사는데 지불해야하는 최대 금액은 
DP[4] = max(P[4], P[3]*1+P[1] , P[2]*2, P[2]+P[1]*2 ) = 8원

     = max(4장 들어있는 카드팩 하나 사는 금액,\
           3장 들어있는 카드팩 하나 사는 금액 + 1장 카드 사는 최대 금액,\
           2장 들어있는 카드팩 하나 사는 금액 + 2장 카드 사는 최대 금액,\ 
           1장 들어있는 카드팩 하나 사는 금액 + 3장 카드 사는 최대 금액 )
     = max(P[4], P[3]+DP[1], P[2]+DP[2], P[1]+DP[3])


카드 5장 사는데 지불해야하는 최대 금액은 
DP[5] = max(P[5], P[4]+P[1] ,P[3]+P[2] \
        ,P[3]+P[1]*2, P[2]*2+P[1], P[2]+P[1]*3, P[1]*5 ) = 9원

     = max(5장 들어있는 카드팩 하나 사는 금액,\
           4장 들어있는 카드팩 하나 사는 금액 + 1장 카드 사는 최대 금액,\
           3장 들어있는 카드팩 하나 사는 금액 + 2장 카드 사는 최대 금액,\
           2장 들어있는 카드팩 하나 사는 금액 + 3장 카드 사는 최대 금액,\
           1장 들어있는 카드팩 하나 사는 금액 + 4장 카드 사는 최대 금액)
           
           
------------------------------------------------

코드

n = int(input()) # 카드의 개수 
p = list(map(int, input().split())) # p 

dp = [0 for _ in range(n+1)]
p = [0]+p

dp[1] = p[1]

for i in range(2,n+1):
    dp[i] = p[i]
    for j in range(1,i):
        dp[i] = max(dp[i], p[j] + dp[i-j])

print(dp[n])

✨후기

dp문제인데 갈피를 못잡아서 이분의 글을 참고해서 이해했다. 어렵다 ㅠ