2021.1.31 [백준] 거스름돈

그리디 알고리즘

 

 

Q

 

www.acmicpc.net/problem/5585

5585번: 거스름돈

 

A

 

가장 큰 금액의 동전부터 계산한다. 

 

k = int(input()) #지불할 액수 입력받기
n = 1000 - k #1000엔에서 지불할 액수를 뺀 거스름돈 계산
result = 0
while n != 0:
    
    if n >= 500:
        result += n // 500
        n = n % 500
    elif n >= 100:
        result += n // 100
        n = n % 100
    elif n >= 50:
        result += n // 50
        n = n % 50
    elif n >= 10:
        result += n // 10
        n = n % 10
    elif n >= 5:
        result += n // 5
        n = n % 5
    elif n >= 1:
        result += n // 1
        n = n % 1
    else:
        break
        
print(result)