728x90
https://www.acmicpc.net/problem/5585
5585번: 거스름돈
타로는 자주 JOI잡화점에서 물건을 산다. JOI잡화점에는 잔돈으로 500엔, 100엔, 50엔, 10엔, 5엔, 1엔이 충분히 있고, 언제나 거스름돈 개수가 가장 적게 잔돈을 준다. 타로가 JOI잡화점에서 물건을 사
www.acmicpc.net
그리디 알고리즘의 대표격이라고 할 수 있는 문제인 것 같다
제한시간: 10분
1. 모든 동전을 내림차순으로 정렬
2. 정렬한 배열을 순회하며 거스름돈을 해당 동전으로 나눈 몫을 카운팅
3. 나눈 몫 * 동전 를 거스름돈에서 빼준다.
coins = [500, 100, 50, 10, 5, 1]
pay = int(input())
change = 1000 - pay
count = 0
for i in coins:
count += change // i
change -= (change // i) * i #change를 i로 나눈 나머지값과 동일하므로 change %= i로 쓰면 더 간단
print(count)728x90
반응형
'Coding Test' 카테고리의 다른 글
| 백준 1439 - 뒤집기 ( Python ) (0) | 2022.12.09 |
|---|---|
| 백준 2217 - 로프 ( Python ) (0) | 2022.12.01 |
| 백준 1541 - 잃어버린 괄호 ( Python ) (0) | 2022.11.27 |
| 백준 11047 - 동전 0 (Python) (0) | 2022.11.25 |
| 백준 11399 - ATM( Python ) (0) | 2022.11.23 |
