[백준] 2294번,python - 동전 2

 

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

 

n, k = map(int,input().split())
li = []
dp = [float('inf')]*(100001)
dp[0] = 0

for _ in range(n):
    li.append(int(input()))

for i in li:
    dp[i] = 1

for i in range(2,k+1):
    for coin in li:
        if i >= coin:
            dp[i] = min(dp[i],dp[i-coin]+1) # 코인 사용 + 코인 사용하고 남은거, 현재 중 작은 것
    

if dp[k] != float('inf'):
    print(dp[k])
else:
    print(-1)