t_거스름돈_87

source	github.com/ndb796/python-for-coding-test
type	📌 개발노트
topics	600-알고리즘 & 코딩테스트 602 그리디
types	문제풀이

문제

동전 500,100,50,10일때 거슬러줘야할 동전의 최소 개수

답

큰화패단위부터 greedy하게 돌려줌.

WHY

큰단위가 작은 단위의 배수이다.
- 500은 100의 배수 100은 50의 배수 ...등
- 이 조건이 어긋나면 그리디하면안됨
- ex) 500 400 100이면 500은 400의 배수가 아니기에 greedy를 쓰면 답이틀림
  - 800일경우 greedy -> 500,100,100,100
  - 정답 -> 400,400