[그리디/Greedy] 이코테 거스름 돈 문제 (Python / 파이썬)

이것이 취업을 위한 코딩 테스트다 with 파이썬 (나동빈 저) 3장 그리디(greedy, 탐욕법) 거스름 돈 문제는 거슬러 주어야 할 돈이 주어졌을 때 거슬러 주어야 할 동전의 최소 개수를 구하는 문제이다.

 

이코테 3장 그리디 거스름 돈 문제 정보

출처

- [한빛미디어] 이것이 취업을 위한 코딩 테스트다 with 파이썬 (나동빈 저)

- https://youtu.be/2zjoKjt97vQ

알고리즘 분류

- 그리디 알고리즘 (greedy algorithm, 탐욕법)

 

거스름 돈 문제 요약

• 카운터에 거스름돈으로 사용할 500원, 100원, 50원, 10원짜리 동전이 무한히 존재한다.
• 손님에게 거슬러 주어야 할 돈이 N원일 때 거슬러 주어야 할 동전의 최소 개수를 구한다.
• 단, 거슬러 줘야 할 돈 N은 항상 10의 배수이다.
  

 

문제 풀이 과정

1. 거슬러 주어야 할 돈 N을 입력받는다.
2. 큰 단위의 동전부터 차례대로 구성된 리스트를 정의한다.
3. 큰 단위의 동전부터 거슬러 줄 동전의 개수를 구하여 출력 값에 더한다.
4. 현재 동전으로 거슬러주고 남은 돈을 N에 저장한다.
5. 가장 작은 단위의 동전까지 반복한다.
6. 거슬러 주어야 할 동전의 최소 개수를 출력한다.

 

코드 및 설명

• N - 거슬러 주어야 할 돈
• coin - 큰 단위의 동전부터 차례대로 구성된 리스트
• count - 거슬러 주어야 할 동전의 개수
• c - 현재 계산 중인 동전
• 시간 복잡도 - O(K) (동전의 종류 K개)

N = int(input())

coin = [500, 100, 50, 10]
count = 0

for c in coin:
    count += N // c  # 거슬러 줄 동전의 개수
    N %= c  # 현재 동전으로 거슬러 주고 남은 돈

print(count)

---

그리디 알고리즘이 정당한 이유는 거슬러 주어야 할 동전의 큰 단위가 작은 단위의 배수가 되기 때문이고, 큰 단위부터 거슬러주게 되면 문제를 해결할 수 있다.

알고리즘을 선택할 때의 정당성과 시간 복잡도를 분석해보는 능력을 길러야겠다.

 

이것이 취업을 위한 코딩 테스트다 with 파이썬 (나동빈 저) 3장 그리디 알고리즘 (greedy algorithm, 탐욕법) 거스름 돈 문제를 파이썬 python으로 풀어보았다.