[Python]알고리즘/백준
[그리디 알고리즘] 5585번 - 거스름돈
[백준] 5585번 - 거스름돈 1) 문제 해결 아이디어 그리디 알고리즘의 대표적인 문제이다. for문에서 화폐단위가 큰 것부터 검사해야 총 동전 수의 최소값을 만들 수 있다. 2) 소스코드 pay = int(input()) # 지불 금액 money = [500, 100, 50, 10, 5, 1] charge = 1000 - pay # 잔돈 res = 0 # 잔돈 개수 for m in money: # 탈출 조건 if(charge == 0): break # 해당 단위로 나눠지면 if((charge // m) != 0): res += charge // m # 잔돈 개수 추가 charge %= m # 잔액 변경 print(res)
