Baekjoon-2294-동전 2

import sys
input = sys.stdin.readline

n,k = map(int, input().split())
values = [0] + [int(input()) for _ in range(n)]
infty = int(1e5)

dp = [0 for _ in range(k+1)]

for i in range(n+1):
    for j in range(k+1):
        coin = values[i]
        if i == 1:
            dp[j] = j//coin if j%coin==0 else infty
        elif j < coin:
            pass
        elif j == coin:
            dp[j] = min(dp[j],1)
        else:
            dp[j] = min(dp[j-coin]+1, dp[j])

if dp[k] == infty:
    print(-1)
else:
    print(dp[k])