[그리디] 3 - 1 거스름돈

# 500원, 100원 ,50원 ,10원으로 거스름돈 N원을 줄 때, 거슬러줘야 할 동전의 최소 개수를 구하기

n = int(input())
count = 0
# 큰 단위의 화폐부터 차례대로 확인
coins = [500, 100, 50, 10]
for coin in coins:
	count += n//coin  # 해당 화폐로 거슬러 줄 수 있는 동전의 개수 세기
    n %= coin
print(count)    

 

화폐의 종류만큼 반복을 수행한다.
화폐의 종류가 K개라고 할 때 시간 복잡도는 O(K)

거스름돈 문제가 그리디 알고리즘으로 해결되는 이유는 가지고 있는 동전 중에서 큰 단위가 항상 작은 단위의 배수이므로 작은 단위의 동전들을 종합해 다른 해가 나올 수 없기 때문이다. 

=> 가장 큰 단위의 화폐부터 가장 작은 단위의 화폐까지 차례대로 확인하여 거슬러 주는작업만 수행하면 된다.

거스름돈 문제에서 화폐의 단위가 서로 배수 형태가 아니라 무작위로 주어진 경우에는 그리디 알고리즘으로 해결할 수 없다. => 다이나믹 프로그래밍