[백준] 11047 동전 0

문제

• N개 종류의 동전이 매우 많을 때 적절히 사용해 합을 K로 만드려고 한다.
• 이때 필요한 동전 개수의 최솟값 구하기

 

• 1 <= N <= 10
  1 <= K <= 100,000,000

 

풀이

• 동전의 최소 개수를 구해야 하므로, 가장 단위가 큰 동전이 필요한 개수만큼 세도록 한다.

 

N, K = map(int, input().split())
coins = [int(input()) for _ in range(N)]
coins.sort()
cnt = 0
while K > 0 :
    coin = coins.pop()
    cnt += K // coin
    K %= coin

print(cnt)

 

References

• 백준 그리디