[baekjoon] 백준 5585번(파이썬): 거스름돈

문제

5585번: 거스름돈

- 잔돈에는 500엔, 100엔, 50엔, 10엔, 5엔, 1엔이 충분히 있다.

- 언제나 거스름돈 개수는 최소한의 잔돈으로 받는다.

- 물건을 사고 카운터에서 1000엔 지폐를 한장 냈을 때, 받을 잔돈의 개수를 구하는 문제이다.

- 타로가 지불할 돈은 1이상 1000미만의 정수이다.

알고리즘

- 문제는 매 상황에서 항상 최선의 선택만 하는 문제로, 그리디 알고리즘 문제라고 볼 수 있다.

- 타로가 지불할 돈을 입력한다.

- 타로가 낸 1000엔에서 지불할 돈을 빼준다.

- 타로에게 줄 거스름돈 개수를 최소한의 잔돈으로 준다.

코드

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

for j in array:
    count += i // j
    i%=j
    if i==0:
        break
print(count)

github

junjange/CodingTest