[파이썬 알고리즘] 거스름돈 문제 풀이

❓ 문제

---

💡 문제 해결 아이디어

---

N원을 거슬러 줘야 할 때, 500원으로 거슬러 줄 수 있을 만큼 거슬러 준다.

그 다음 100원, 50원, 10원을 차례대로 거슬러 주면 된다.

즉, 최적의 해를 빠르게 구하기 위해서는 가장 큰 화폐 단위부터 돈을 거슬러 주면 된다.

아래 예제로 알아보자.

>  N = 1,260인 경우

---

• [Step 0] 초기 단계 - 남은 돈: 1,260원
  • 500원짜리로 거슬러 준다.
  • 1,260 - (500*2) = 260
• [Step 1] 남은 돈: 260원
  • 100원짜리로 거슬러 준다.
  • 260 - (100*2) = 60
• [Step 2] 남은 돈: 60원
  • 50원짜리로 거슬러 준다.
  • 60 - (50*1) = 10
• [Step 3] 남은 돈: 10원
  • 10원짜리로 거슬러 준다.
  • 10 - (10*1) = 0
• [Step 4] 남은 돈: 0원

이 방법이 최적의 해인 이유?
가지고 있는 동전 중에서 큰 단위가 항상 작은 단위의 배수이므로 작은 단위의 동전들을 종합해 다른 해가 나올 수 없기 때문에 최적의 해이다.

만약 화폐 단위가 500원, 400원, 100원이라면?

만약 800원을 거슬러 주어야 한다면 그리디 알고리즘에 의해 500원 1개, 100원 3개로 거슬러주게 된다.

하지만 최적의 해는 400원 2개로 거슬러 주는 것이다.

이와 같이 큰 단위가 작은 단위의 배수가 아닐 경우 오류가 발생하게 된다.

우리는 문제 풀이를 위한 최소한의 아이디어를 떠올리고 이것이 정당한지 검토할 수 있어야 한다.

✔️ 파이썬 답안 예시

---

n = 1260
count = 0

# 큰 단위의 화폐부터 차례대로 확인하기
coin_types = [500, 100, 50, 10]

for coin in coin_types:
    count += n // coin # 해당 화폐로 거슬러 줄 수 있는 동전의 개수 세기
    n %= coin

print(count)

🕓 시간 복잡도 분석

---

화폐의 종류가 K라고 할 때, 시간 복잡도는 O(K)이다.

이는 거슬러줘야 하는 금액과는 무관하게 화폐(동전)의 종류 만큼만 반복문을 수행한다는 것을 의미한다.

Notice: 이 게시물은 한빛미디어의 이것이 코딩 테스트다 영상과 교재를 참고하였습니다.