greedy: 거스름돈

문제 정의/조건
당신은 음식점의 계산을 도와주는 점원이다. 카운터에는 거스름돈으로 사용할 500원, 100원, 50원, 10원짜리 동전이 무한히 존재한다고 가정한다. 손님에게 거슬러 줘야 할 돈이 N원일 때 거슬러 줘야 할 동전의 최소 개수를 구하라. 단, 거슬러 줘야할 돈 N은 항상 10의 배수이다.

로직
N이 가장 작은 동전의 단위인 10의 배수이기 때문에 0원에 도달할 수 있다.
거슬러 줄 동전의 최소 개수를 구하려면 큰 단위의 동전부터 거슬러주면 된다.
나머지는 다음으로 큰 단위의 동전으로 거슬러 준다.

내가 짠 코드

n = int(input())
n = 1260
coin_lst = [500, 100, 50, 10]
result = 0  # 거슬러 준 동전의 개수

for coin in coin_lst:
    result += n // coin
    n = n % coin
print(result)
    

시간 복잡도
화폐의 종류가 K라고 할때, 소스코드의 시간복잡도는 O(K)이다.
거슬러줘야하는 금액과는 무관하며 동전의 총 종류에만 영향을 받는다.