백준 5585번 거스름돈 [그리드 알고리즘]

백준 5585번 거스름돈

주어진 동전의 종류는 [500, 100, 50, 10, 5, 1] 이 있으며, 물건 구매를 위해 1000엔을 전달한다.
입력 받은 값은 물건의 가격이며, 이때 거슬러 받아야하는 잔돈의 동전 개수 중 최소 개수를 구하라.

 

[문제풀이과정]

1. 주어진 동전의 종류가 배수 관계를 가지고 있어서 그리드 알고리즘을 사용할 수 있다.
2. 거슬러 받는 동전의 개수를 최소로 만들기 위해서는,
   현재 남은 금액에서 가장 큰 단위의 동전을 최대한 많이 사용하는 방식이 가장 유리하다

 

[코드]

price = int(input())
coins = [500,100,50,10,5,1]
change = 1000 - price
result = 0
for coin in coins:
    if change == 0:
        break
    
    if change//coin > 0:
        result += change//coin
        change%=coin
print(result)