[Algorithms] 동적 계획법(Dynamic Programming)-동전 교환(냅색 알고리즘)

 

• 앞의 가방 문제와 마찬가지로 냅색 알고리즘을 사용하여 푼다 
• 다른 점은 minimum 값을 구한다는 것이다 

if __name__=='__main__':
 
    n = int(input())
    coins = list(map(int, input().split()))
    money = int(input())
 
    dyn = [1000]*(money+1) # 동전이 1 <= M <= 500 이므로 넉넉하게 큰 값을 1000으로 주었다
    dyn[0] = 0
 
    for coin in coins:
        for i in range(coin, money+1):
            dyn[i] = min(dyn[i-coin]+1, dyn[i])
 
    print(dyn[money])