Problem Solving/Online Judge
[BOJ] #5585 - 거스름돈
se0m
2021. 6. 25. 11:28
5585번: 거스름돈
타로는 자주 JOI잡화점에서 물건을 산다. JOI잡화점에는 잔돈으로 500엔, 100엔, 50엔, 10엔, 5엔, 1엔이 충분히 있고, 언제나 거스름돈 개수가 가장 적게 잔돈을 준다. 타로가 JOI잡화점에서 물건을 사
www.acmicpc.net
** 문제 유형
- 그리디
** 풀이
- 거스름 돈의 최소 개수 계산
- 가장 기초적인 탐욕 알고리즘 문제 유형으로, 단순히 '큰 화폐 단위' 순서대로 잔돈을 거슬러 주면 최적의 해를 구할 수 있음
changes = 1000 - int(input())
cnt = 0
for i in [500, 100, 50, 10, 5, 1]:
cnt += changes // i
changes %= i
print(cnt)