[백준]5585번 거스름돈 - 그리디

 

n = int(input())

n = 1000 - n
answer = 0
while True:
    if n // 500 >= 1:
        answer = answer + (n // 500)
        n = n - ((n // 500) * 500)
    elif n // 100 >= 1:
        answer = answer + (n // 100)
        n = n - ((n // 100) * 100)
    elif n // 50 >= 1:
        answer = answer + (n // 50)
        n = n - ((n // 50) * 50)
    elif n // 10 >= 1:
        answer = answer + (n // 10)
        n = n - ((n // 10) * 10)
    elif n // 5 >= 1:
        answer = answer + (n // 5)
        n = n - ((n // 5) * 5)
    else:
        answer = answer + n
        n = 0
    if n == 0:
        print(answer)
        break

 

코드 설명

잔돈을 구하는 것이기 때문에 1000-n 을 통해 잔돈으로 갱신하여 준다. 반복문을 수행하며 각 동전별로 몫이 1 이상이라면 그 동전을 사용한다. 그렇지 않은 경우에는 1원 짜리를 이용한다. n == 0 이 되는 시점에 반복문을 종료한 후 정답을 출력 한다.

 

Point : 5엔으로도 줄 수 없을 경우 1원을 사용한다. 1원의 경우 가장 마지막 연산이 되기 때문에 갯수 만큼 더하고 n = 0 으로 만들어 준다.