[ Baekjoon : python ] 백준 11052번 카드 구매하기 - 다이나믹프로그래밍

[  BAEKJOON ONLINE JUDGE  ] 11052 카드 구매하기 _ Python 파이썬

 

" 문제 "

 

제목 :www.acmicpc.net/problem/11052

11052번: 카드 구매하기

---

" 아이디어 "

D[i] = 카드 i개를 구매하는 최대 비용

P[j] = j번째 카드팩의 비용

 

i-j개의 카드 + j번째 카드팩(마지막에 구매) = i개의 카드 (최종)

-> D[i] = max ( D[i-j] + P[j] )   ( j>=1, j<=i)

D[0] = 0 (초기값)

---

" 코드 "

 

n = int(input())
p = [0] + list(map(int, input().split()))
 
d = [0]*(n+1)
for i in range(1,n+1):
  for j in range(1,i+1):
    d[i] = max(d[i], d[i-j]+p[j])
 
print(d[n])

---

" 참고자료 "