[이코테][Chapter 3][문제] 1. 거스름돈

[문제]

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

 

[입력]

1260

[출력]

6

---

가장 대표적이고, 가장 간단한 그리디 알고리즘 문제이다.

접근법 : 제일 큰 동전부터 거슬러주면서, 갯수를 하나씩 센다.

 

import time

n = 1260 #거스름돈
count = 0 #동전의 개수
coin_types = [500,100,50,10] #동전의 종류

start_time = time.time()

for coin in coin_types:
    count += n // coin #몫. 동전의 개수 세기
    n %= coin #나머지. x원의 동전을 바꾼 후의 나머지.

print(count)

end_time = time.time()
print("프로그램 작동 시간 : ", end_time - start_time)