[알고리즘][파이썬]5585-거스름

 

 

문제

 

 

 

코드

import sys

n = 1000-int(sys.stdin.readline())

M = [500, 100, 50, 10, 5, 1]
count = 0

for money in M:
    if n == 0:
        break
    
    count += n // money #금액이 큰 거스름돈 먼저 잔돈 개수 계산
    n %= money
    
print(count)

 

 

문제설명
잔돈의 개수가 최소가 되도록 해야 하는 문제이다.

 

접근방법
그리디 알고리즘을 사용한다.

 

코드설계
-액수가 큰 지폐를 최대한 많이 사용해야하기 때문에

가장 큰 잔돈 500부터 내림차순으로 M에 저장한 후 for문을 돌린다.

-for문을 돌면서 money로 거스름돈을 나눈 몫(해당 잔돈 개수)을 결괏값에 더한다.

-그 후에 남은 거스름돈을 계산하고 남은 거스름돈이 없을 때까지 이 과정을 반복한다.

 

 

 

❗그리디 알고리즘❗

-탐욕 알고리즘
-선택의 순간마다 당장 눈앞에보이는 최적의 상황만을 쫒아 최종적인 해답에 도달
- 여러 경우 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행하여 최종적인 해답에 도달

[알고리즘] 탐욕 알고리즘(Greedy Algorithm) - 하나몬