백준 (boj) 파이썬 - 11052 번 : 카드 구매하기 (DP)

문제 링크 : https://www.acmicpc.net/problem/11052

11052번: 카드 구매하기

 

 

 

 

---

 

문제 분류 : 다이나믹 프로그래밍 https://infinitt.tistory.com/246

알고리즘 - 다이나믹 프로그래밍 (Dynamic Programming)

 

작은 문제부터 생각해본다. 카드를 한개 사는법부터

dp[i] = 카드 i개 구매하는 최대 가격 , p[k] = k개가 들어있는 카드팩 가격 이라고 했을때

카드를 i개 구매하는 최대 비용은 다음과 같다.

p[1] + dp[i-1]

p[2] + dp[i-2]

p[3] + dp[i-3]

'''''

'''''

p[i] + dp[0]

 

따라서 점화식은 dp[i] = p[k] + dp[i - k] 가 된다.

 

 

*정답 코드 (Python)

N = int(input())
p = [0] + list(map(int,input().split()))
dp = [0 for _ in range(N+1)]


for i in range(1,N+1):
    for k in range(1,i+1):
        dp[i] = max(dp[i], dp[i-k] + p[k])
print(dp[i])