[백준] 16194 카드구매하기2 (python)

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

16194번: 카드 구매하기 2

 

 

✋ 접근방법

dp를 이용해서 풀이

중복해서 사용가능하므로 knapsack과는 다르게,

앞에서부터 각 무게의 최소값을 찾아나가면 됨

 

👏 코드

# knapsack 알고리즘 이용 -> 중복허용 가능하므로 dp 갱신부분의 j루프를 앞에서부터 진행!
N = int(input())
arr = [0]+ list(map(int,input().split()))
# index : 카드개수, value : 최소가격
dp = arr.copy()

for i in range(1,N+1):
    for j in range(1,i+1):  # 중복허용가능하므로, 앞에서부터 진행
        dp[i] = min(dp[i], dp[i-j] + arr[j])
    # print(i, dp)



print(dp[N])