효율적인 화폐 구성

 

해결법

이 문제도 보텀업 방식으로 푸는 문제이다. 리스트 d에 작은 수부터 체크하면서 푼다. 

이 문제의 핵심 풀이 방식은 지금의 숫자와 비교했을 때, 동전의 숫자만큼 뺀 숫자가 존재하면 당연히 동전 수만큼 더한 수도 존재한다는 것이다. 

 

풀이

n, m = map(int, input().split())
ary = []

for i in range(n):
    ary.append(int(input()))

d = [10001] * (m+1)

d[0] = 0
# 동전 수만큼 반복
for i in range(n):
    # 가장 작은 동전 수부터 구하려는 목표 수까지 반복
    for j in range(ary[i], m+1):
        # (i-k)원을 만들 수 있으면
        if d[j - ary[i]] != 10001:
            d[j] = min(d[j], d[j-ary[i]]+1)

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

반복문에서 동전 수만큼 반복하고 중첩문으로 가장 작은 동전 수부터 구하려는 목표 수까지 반복한다. 그리고 d[j - ary[i])가 만들 수 있는 숫자이면 비교해서 작은 수를 넣어준다.