이것이 코딩테스트다 with 파이썬 - Chp 8. 다이나믹 프로그래밍_5. 효율적인 화폐 구성

n, m = map(int, input().split())
array = []
for i in range(n):
    array.append(int(input()))

d = [10001] * (m + 1)

d[0] = 0
for i in range(n):
    for j in range(array[i], m+1):
        if d[j - array[i]] != 10001:
            d[j] = min(d[j], d[j -array[i]] + 1)

if d[m] == 10001:
    print(-1)
else:
    print(d[m])

d에 10001을 미리 할당해놓고 이후에 메모이제이션을 통해서 값을 새로 할당하는 방식을 사용한다.