이코테-chapter3:그리디 거스름돈

# 그리디 알고리즘, 거스름돈, python3

""" 문제
1. 500원, 100원, 50원, 10원짜리 동전이 무한히 존해한다.
2. 손님에게 거슬러 줘야 할 돈이 N원일 때 거슬러줘야 할 동전의 최소 개수를 구하라.
3. 단, 거슬러 줘야 할 돈 N은 항상 10의 배수이다.
"""

""" 문제 풀이
- 그리디 알고리즘을 활용.
- 가장 큰 화폐단위부터 돈을 거슬러줌.
- 시간복잡도 O(N)
"""

n = 1260
count = 0

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

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

print(count)

출처 && 깃허브

이것이 취업을 위한 코딩 테스트다 with python

github