10. 다이나믹 프로그래밍(효율적인 화폐 구성)

# 효율적인 화폐 구성
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