[백준 5585 거스름돈] 그리디 알고리즘 활용하기

이번에 해결한 문제는 다음과 같다.

www.acmicpc.net/problem/5585

5585번: 거스름돈

 

 

 

다음과 같은 아이디어를 바탕으로 아래와 같이 코드를 작성하였다.

money = int(input())
coin = [500,100,50,10,5,1]
count,i = 0,0
money = 1000 - money

while money > 0 :
    if money > coin[i] :
        count += 1
        money -= coin[i]
    elif money == coin[i]:
        count += 1
        break
    else :
        i += 1

print(count)

 

 

책에서 제시하는 문제는 살짝 다르므로, 책에서 제시한 알고리즘을 이 문제에 적용시키면 다음과 같은 코드가 작성된다.

n = int(input())
count = 0
coin_types = [500,100,50,10,5,1]
n = 1000-n

for coin in coin_types :
    count += n // coin
    n %= coin

print(count)