거스름돈

지침

동전 값의 합이 정확한 거스름돈 금액과 같아지도록, 손님에게 줘야 할 동전의 최소 개수를 정확히 구해요.

예를 들어

• 입력이 15이고 동전이 [1, 5, 10, 25, 100]이라면, 니켈(5) 한 개와 다임(10) 한 개, 즉 [5, 10]을 반환해야 해요
• 입력이 40이고 동전이 [1, 5, 10, 25, 100]이라면, 니켈(5) 한 개와 다임(10) 한 개, 쿼터(25) 한 개, 즉 [5, 10, 25]를 반환해야 해요

엣지 케이스

• 알고리즘이 어떤 동전 집합에 대해서도 동작하나요?
• 음수 거스름돈을 요청할 수 있나요?
• 가장 작은 동전 값보다 작은 거스름돈을 요청할 수 있나요?

---

출처

Software Craftsmanship - Coin Change Kata