https://www.acmicpc.net/problem/5585
5585번: 거스름돈
타로는 자주 JOI잡화점에서 물건을 산다. JOI잡화점에는 잔돈으로 500엔, 100엔, 50엔, 10엔, 5엔, 1엔이 충분히 있고, 언제나 거스름돈 개수가 가장 적게 잔돈을 준다. 타로가 JOI잡화점에서 물건을 사
www.acmicpc.net
n = int(input())
cash = [500, 100, 50, 10, 5, 1]
k = 1000 - n
cnt = 0
for i in cash:
cnt += k // i
k %= i
print(cnt)
그리디 알고리즘을 거스름돈 문제를 예시로 들어서 공부했기 때문에 쉽게 풀 수 있었다!
'알고리즘 > 백준' 카테고리의 다른 글
| 백준 10162: 전자레인지 (Python) (0) | 2021.09.30 |
|---|---|
| 백준 2217: 로프 (Python) (2) | 2021.09.29 |
| 백준 1026: 보물 (Python) (0) | 2021.09.29 |
| 백준 1541: 잃어버린 괄호 (Python) (0) | 2021.09.27 |
| 백준 1931: 회의실 배정 (Python) (0) | 2021.09.27 |