알고리즘
백준) 거스름돈-python
1일1공부실천하자
2023. 1. 30. 00:53
https://www.acmicpc.net/problem/5585
5585번: 거스름돈
타로는 자주 JOI잡화점에서 물건을 산다. JOI잡화점에는 잔돈으로 500엔, 100엔, 50엔, 10엔, 5엔, 1엔이 충분히 있고, 언제나 거스름돈 개수가 가장 적게 잔돈을 준다. 타로가 JOI잡화점에서 물건을 사
www.acmicpc.net
a = int(input())
a = 1000 - a
answer = 0
while a > 0:
if a >= 500:
answer += a // 500
a = a % 500
elif a >= 100:
answer += a // 100
a = a % 100
elif a >= 50:
answer += a // 50
a = a % 50
elif a >= 10:
answer += a // 10
a = a % 10
elif a >= 5:
answer += a // 5
a = a % 5
elif a >= 1:
answer += a // 1
a = a % 1
print(answer)
사실 그리디의 기본 중 기본인 문제였다.
설명할 것은 딱히 없지만 하나 중요한 점은,
해당 풀이가 성립하기 위해선 거스름돈이 각각의 거스름돈으로 나뉘어야 성립이 가능하다.
즉, 큰 수가 다른 작은 수들로 나누어 떨어질 경우에만 성립이 가능한 풀이이다.