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

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

16194번: 카드 구매하기 2

 

 

---

 

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

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

 

 

 

 

 

 

카드 구매하기 1 을 먼저 풀었다면 어렵지 않은 문제같다.

카드 구매하기 1은 최대값(max)를 구하고

2는 최소값을 구한다는 차이밖에 없다. 점화식도 같기 때문에 이 포스팅에서는 생략..

https://infinitt.tistory.com/250

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

 

*정답코드 (Python)

N = int(input())

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


for i in range(1, N+1):
    for k in range(1, i+1):
        if dp[i] == False :
            dp[i] = dp[i-k]+p[k]
        else :
            dp[i] = min(dp[i], dp[i-k]+p[k])

print(dp[N])

(습관처럼 리스트를 0으로 초기화시켜 선언했지만, min함수를 사용해야하기 때문에, False로 값을 바꿔줬다.)