📁 코딩테스트 준비/Python
[그리디 / python] 거스름돈
박개봄
2022. 11. 10. 14:14
728x90
문제풀이
n=int(input())
count=0
coin_types = [500,100,50,10]
for coin in coin_types:
count+=n//coin
n%=coin
print(count)
*그리디 알고리즘 적용이 가능한 이유
가지고 있는 동전 중, 큰 단위가 항상 작은 단위의 배수이므로, 작은 단위의 동전들을 종합해 다른 해가 나올 수 없다!
728x90