728x90
5585번: 거스름돈
타로는 자주 JOI잡화점에서 물건을 산다. JOI잡화점에는 잔돈으로 500엔, 100엔, 50엔, 10엔, 5엔, 1엔이 충분히 있고, 언제나 거스름돈 개수가 가장 적게 잔돈을 준다. 타로가 JOI잡화점에서 물건을 사
www.acmicpc.net
분석
가지고 있는 동전 중에서 큰 단위가 항상 작은 단위의 배수이므로 작은 단위의 동전들을 종합해 다른 해가 나올 수 없기 때문에 그리디 알고리즘으로 해결 가능
풀이
"""
500엔, 100엔, 50엔, 10엔, 5엔, 1엔짜리 동전이 무수히 많은 경우
1000엔 지폐를 한장 냈을 때, 받을 잔돈에 포함된 잔돈의 개수
지불할 돈 입력
"""
m=int(input())
c=[500, 100, 50, 10, 5, 1]
n=1000-m
cnt=0
for i in c:
cnt += n//i # 해당 화폐로 거슬러 줄 수 있는 동전의 개수 체크
n%=i
print(cnt)
728x90