[Algorithm] Greedy - ‘거스름 돈’

📣 학습한 내용을 정리한 글입니다.

Greedy Algorithm 문제입니다. 문제에 대한 내용과 풀이 그리고 결과를 간단하게 작성하였으니 참고바랍니다.
풀이 언어 : Python

문제 설명

---

내용

음식점에서 거스름돈으로 사용할 500원, 100원, 50원, 10원짜리 동전이 무한히 존재한다고 가정하자.
손님에게 거슬러주어야 할 돈이 N원일 때 거슬러주어야 할 동전의 최소의 개수는?
(단, 거슬러 주어야 할 돈 N은 항상 10의 배수이다.)

입력

N원을 입력받는다.(N은 0보다 큰 10의 배수)

출력

동전의 최소 개수가 출력된다.

문제 풀이

---

Greedy Algorithm 참고내용

• 일반적인 상황에서 Greedy Algorithm은 최적의 해를 보장할 수 없을 때가 많다.
  
• 하지만 Coding Test에선 일반적으로 Greedy Algorithm문제에서 이를 사용해 얻은 해가 최적의 해가 되는 경우가 많다.
  위 참고사항을 준수하며, 풀어보자.
  
• 가장 큰 화폐 단위부터 돈을 거슬러줄 수 있을 만큼 거슬러주면 된다.
  N원은 10의 배수이기에 가지고 있는 동전 단위의 가장 큰 화폐 부터 최대 개수로 거슬러 주면 동전의 최소의 개수가 나온다.

작성 코드

Python

---

참고 : ‘동빈나’님의 (이코테 2021 강의 몰아보기) 2. 그리디 & 구현 영상

---