※ 본 문제는 코드업에서 발췌하였습니다.
어떤 가게의 욕심쟁이 점원은 거스름돈을 나눠줄때 거스름돈의 개수를 적게해서 주고자 한다.
거스름돈을 입력 받아 점원이 줄 수 있는 최소 거스름돈의 개수를 출력하시오.
예를 들어 54520원인 경우,
거스름돈으로 50000원권 1장, 1000원권 4장, 500원 1개, 10원 2개 해서 총 8개이다.
(※ 현재 우리나라가 사용하고 있는 화폐를 사용한다. 10원 50원 100원 500원 1,000원 5,000원 10,000원 50,000원)
거스름돈 n이 입력된다. ( n은10이상의 int 범위 )
최소 거스름돈의 개수를 출력한다.
n = int(input())
count = 0
coin_types = [50000, 10000, 5000, 1000, 500, 100, 50, 10]
for coin in coin_types: # coin_types를 for문 돌면서
count += n // coin # count에 n을 coin_types로 나눈 몫을 더한다.
n = n % coin # n에는 n을 coin_types로 나눈 나머지를 대입하면서
# 나눌 값을 줄여나감
print(count)
그리디 알고리즘하면 가장 먼저 떠오르는 문제이다. 쉬운 문제이지만 이런 문제를 자주 접하고 풀어봄으로써 그리디 알고리즘에 더욱 친숙해지도록 하는 것이 현재의 목표이다.