백준 11047 동전 0 - 파이썬

import sys
input = sys.stdin.readline

N, K = map(int, input().split())
coins = []
count = 0

coins = [int(input()) for _ in range(N)]

coins.sort(reverse=True)

for coin in coins:
  count += K // coin
  K = K % coin
  if K == 0: break

print(count)

---

동전이 오름차순으로 입력되는데 우리는 필요한 동전 개수의 최솟값을 출력해야하기 때문에 내림차순 정렬을 한다.

 

1. K원을 큰 동전부터 나눈 후 몫을 count 한다.

ex) 4200원이면 4200 // 1000 > 동전 4개 카운트

2. K원을 큰 동전으로 나눈 나머지를 다시 반복해서 나눌 수 있도록 K에 넣는다.

ex) 4200 % 1000 > 200원

 

남은 200원으로 반복문 수행, 남은 돈이 0이 될 때까지 반복