[파이썬/Python] 백준 5585번: 거스름돈

📌 문제 : 백준 5585번

---

📌 문제 탐색하기

price : 지불할 돈 (1 ≤ price < 1000)
coins : 잔돈 유형 (500, 100, 50, 10, 5, 1)

✅ 입력 조건
1. 지불해야 할 돈 1개 입력
✅ 출력 조건
1. 1000엔을 낸 상황
2. 거스름돈 개수가 가장 적은 잔돈
3. 받을 잔돈에 포함된 잔돈의 개수 출력

먼저, 지불한 1000엔에서 입력된 지불할 돈을 뺀다.

남은 돈을 큰 동전 가격부터 나눈다.

나눈 몫은 잔돈 개수에 더해주고, 남은 나머지는 그 다음으로 큰 동전 가격으로 나눠주는 과정을 반복해서 잔돈 개수를 구한다.

가능한 시간복잡도

가격 입력받기 → $O(1)$
for문을 돌며 잔돈 계산하기 → $O(6) = O(1)$

최종 시간복잡도
$O(1)$로 제한 시간 내에 연산이 가능하다.

알고리즘 선택

6개의 동전 유형을 for문으로 돌면서 잔돈 개수 계산하기

---

📌 코드 설계하기

1. 동전 리스트 선언
2. price 입력
3. 받아야 할 잔돈 계산
4. for문으로 동전 가격을 나누기 반복

---

📌 시도 회차 수정 사항

---

📌 정답 코드

import sys

input = sys.stdin.readline

# 1. 동전 리스트 선언
coins = [500, 100, 50, 10, 5, 1]

# 2. price 입력
price = int(input())

# 3. 받아야 할 잔돈 계산
left = 1000 - price

# 4. for문으로 동전 가격을 나누기 반복
count = 0

for coin in coins:
    if left == 0:
        break

    count += left // coin
    left = left % coin

print(count)

• 결과
  

---

📌 회고

• 문제가 받아야 할 잔돈을 계산하는 문제였다. 유사한 그리디 문제인 지불할 돈의 개수를 구하는 문제로 착각해서 받아야 할 잔돈 구하는 단계를 빠트렸다. 익숙한 문제라고 자만해선 안되겠다.