[백준] 동전2 python

동전2 문제를 다이나믹 프로그래밍으로 풀어 보았다.

import sys
def main():
    K, N = map(int, sys.stdin.readline().split())
    coins = []
    for _ in range(K):
        coins.append(int(sys.stdin.readline()))
 
    d = [-1 for _ in range(N+1)]
    d[0] = 0
    for i in coins:
        if(i<=N):
            d[i] = 1
    
    # dp : 사용하는 동전 수
 
    for i in coins:
        for j in range(i, N+1):
            if(d[j-i]==-1):
                continue
            elif(d[j]==-1 or d[j]>d[j-i]+1):
                d[j] = d[j-i]+1
    
 
    print(d[N])
 
 
if __name__ =="__main__":
    main()