[이것이 코딩테스트다] Greedy-거스름돈

거스름돈 문제 (Greedy Algorithm)

문제 설명

당신은 음식점의 계산을 도와주는 점원입니다. 손님에게 거슬러 줘야 할 돈이 n원일 때, 가장 적은 수의 동전으로 거슬러 주는 방법을 구하세요.

사용 가능한 동전의 종류는 500원, 100원, 50원, 10원입니다.
(단, 각 동전은 무한히 존재한다고 가정합니다.)

---

입력 조건

• 거슬러 줘야 할 금액 n (정수)

---

출력 조건

• 최소한의 동전 개수를 출력

---

입력 예시

n = 1260

---

출력 예시

6

💡 500 × 2 + 100 × 2 + 50 × 1 + 10 × 1 = 1260 → 총 6개

---

문제 풀이

• 가장 큰 단위의 동전부터 차례대로 거슬러준다.
• 그리디 알고리즘(Greedy Algorithm) 을 활용하여 매 순간 최선의 선택을 한다.
• Python의 set은 순서가 보장되지 않으므로, 반복을 위해선 list나 sorted() 사용을 권장함.

---

주의

 

coin_type = {500, 100, 50, 10} # set (집합) → 순서가 없기 때문에 결과가 일정하지 않음

 

 

수정 예시

coin_type = [500, 100, 50, 10] # list로 순서를 명확히 함

---

코드 (Python)

 

n = 1260
count = 0

coin_type = [500, 100, 50, 10]  # 동전 종류 (내림차순 정렬된 리스트)

for coin in coin_type:
    count += n // coin      # 해당 동전으로 거슬러 줄 수 있는 개수
    n %= coin               # 나머지 금액으로 갱신

print(count)

---

핵심 포인트

• 그리디 알고리즘은 항상 최적의 해를 보장하진 않지만, 이 문제에서는 동전이 큰 단위부터 정렬되어 있기 때문에 정확한 결과를 도출할 수 있음.
• 집합(set)은 순서가 보장되지 않으므로, 리스트(list) 를 사용하는 것이 안전하다.