효율적인 화폐 구성

p. 226

 

n,m=map(int, input().split())

array=[]
for _ 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):
    d[j]=min(d[j], d[j-array[i]]+1)

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

주어진 화폐 단위의 배수별로 개수를 구한다.

개수를 구하면서 최소한의 화폐 개수를 찾는다.