그리디 알고리즘이란
지금 상황에서 좋은 것만 고르는 법
– 큰 순서대로
– 작은 순서대로
예제 3-1 변화
당신은 식당의 금전 등록기를 돕는 점원입니다. 계산대에서 거스름돈으로 쓸 수 있는 500원, 100원, 50원, 10원짜리 동전이 무수히 많다고 하자. 고객에게 돌려줄 돈 N이 1원이 되었을 때 돌려받을 코인의 최소 개수를 찾아라. 그러나 반환되는 돈 N은 항상 10의 배수입니다.
여기서 ‘최소한의 코인으로 돌려줘야’ 하기 때문에 ‘가장 큰 통화 단위부터’ 돈을 돌려주는 것이 중요합니다!
우리는 다음과 같은 방법으로 문제를 해결할 것입니다.
1. 500원만큼 돌려준다.
2. 100원은 최대한 돌려주세요.
3. 50원만큼 돌려준다.
4. 남은 만원은 10원 단위로 환불됩니다.
Python에서의 구현은 다음 코드와 같습니다.
def calculate(n):
count = 0
coin_types = ('500', '100', '50', '10')
for coin in coin_types: # coin_types에 있는 값들을 순서대로 순회
count += n//coin # 전체 n을 coin으로 나눈 몫 = 거슬러 준 동전의 개수
n %= coin # 거슬러주고 남은 금액
return count