[알고리즘] 거스름돈 동전의 최소 개수 구하기 - 그리디 알고리즘, 탐욕 알고리즘

문제

당신은 음식점의 계산을 도와주는 점원이다. 카운터에는 거스름돈으로 사용할 500원, 100원, 50원, 10원짜리 동전이 무한히 존재한다고 가정한다. 손님에게 거슬러 줘야 할 돈이 N원일 때 거슬러줘야 할 동전의 최소 개수를 구하라. 단, 거슬러 줘야 할 돈 N은 항상 10의 배수이다.

 

문제 접근 방법

가장 큰 화폐 단위부터 돈을 거슬러 주기

 

코드

n = int(input())
count = 0

coin_types = [500, 100, 50, 10]

for coin in coin_types:
	count += n // coin
    n %= coin
    
    print(n)

 

문제와 풀이의 출처는 '이것이 취업을 위한 코딩 테스트다 with 파이썬' 입니다.