[Python]16194. 카드 구매하기 2

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

16194번: 카드 구매하기 2

---

점화식 dp[i] 를 구하기 위해선

 

p[1] + dp[i-1]

p[2] + dp[i-2]

p[3] + dp[i-3]

...

p[j] + dp[i-j]

 

까지 구해야 하며, 주어진 문제조건에 따라 이 중 에서 가장 작은 값이 dp[i]가 된다.

 

다시 말해, dp[i] = min(p[1] + dp[i-1], p[2] + dp[i-2], p[3] + dp[i-3], ... , p[j] + dp[i-j])

 

여기서 범위는 1<=i<=n, 1<=j<=i 이므로 이중 포문을 이용한 Bottom-up으로 문제를 해결한다.

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