# 효율적인 화폐 구성
n, m = map(int,input().split())
money = []
for _ in range(n):
money.append(int(input()))
# Step 0(초기화)
# 각 인덱스에 해당하는 값으로 INF의 값을 설정
# 이는 특정 금액을 만들 수 있는 화폐구성이 가능하지 않다는 의미를 가짐
d = [10001] * (m+1)
d[0] = 0
# Step 1
# 첫번째 화폐 단위 money[0]를 확인
for i in money:
for j in range(i, m+1):
if d[j-i] != 10001:
d[j] = min(d[j], d[j-i]+1)
if d[m] == 10001:
print(-1)
else:
print(d[m])
Uploaded by Notion2Tistory v1.1.0