[그리디] 거스름돈

▷출처: 이것이 코딩 테스트다 with 파이썬 - 한빛미디어

 

 

Q. 손님에게 돈을 거슬러줄 때 거슬러줘야 할 동전의 최소 개수를 구해야한다고 생각해보자.

 

해결 방법: 가장 큰 화폐 단위부터 돈을 거슬러 주는 것이다.

 

여기서 생각해볼 점은 이것이 가능한 이유이다. 가지고 있는 동전 중에서 큰 단위가 항상 작은 단위의 배수이기 때문에 작은 단위의 동전들을 종합해 다른 해가 나올 수 없기 때문이다.

※문제를 풀 때 이러한 점들에 대해서 잘 생각해보기!

n = 1260

coin_types = [100, 500, 10, 50]
coin_types.sort(reverse=True)

result = 0

for i in coin_types:
    result += n//i
    n %= i

print(result)

# coin_types를 보면 가장 큰 단위인 500이 100,10,50의 배수임을 알 수 있다. 따라서 성립!

# 무작위의 coin_types를 sort(reverse=True)를 통해 큰 수부터 정렬했다.