[ 백준/python ] 5585 : 거스름돈

- 문제

 

- 제출

거스름돈 개수가 최소인 경우를 찾는 문제이다. 즉, 지불하고 남은 돈을 최대한 큰 단위의 잔돈으로 거슬러 주는 방법을 찾는 것이다.

따라서, 거슬러 줘야 할 금액이 잔돈 단위보다 크다면 해당 잔돈을 뺀 금액을 남은 금액이라고 하고 거스름돈 개수를 증가시키면 된다.

 

N = int(input())

def changes(N):
    change = 1000 - N
    coins = [500,100,50,10,5,1]
    count = 0
    
    for c in coins:
        while change >= c:
            change -= c
            count += 1
        else:
            continue
    print(count)

changes(N)

 

거스름돈의 단위도 제시되어 있고, 그리디 알고리즘의 가장 기본적인 규칙에 해당하는 문제인 것 같다.

그리디 알고리즘을 단 번에 이해할 수 있는 문제라고 생각한다 :)