[BOJ] #5585 - 거스름돈
2021. 6. 25. 11:28ㆍProblem Solving/Online Judge
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)
'Problem Solving > Online Judge' 카테고리의 다른 글
| [BOJ] #2012 - 등수 매기기 (0) | 2021.06.25 |
|---|---|
| [BOJ] #1439 - 뒤집기 (0) | 2021.06.25 |
| [BOJ] #11053 - 가장 긴 증가하는 부분 수열 (0) | 2021.06.22 |
| [BOJ] #12865 - 평범한 배낭 (0) | 2021.06.22 |
| [BOJ] #1904 - 01타일 (0) | 2021.06.22 |