[백준] 5585번 거스름돈 (파이썬)

 

문제

 

5585번: 거스름돈

 

 

 

정답 소스코드 (Python)

 

cost=int(input())
cost=1000-cost
result=0

def calculate(value):
    global cost,result
    if cost>=value:
        result+=cost//value
        cost-=value*(cost//value)


for ele in [500,100,50,10,5,1]:calculate(ele)

print(result)

 

풀이  (Python)

 

그리디 문제의 제일 기초적인 거스름돈 문제이다.

간단하게 입력받은 int값을 1000원에 나눠준 후 500,100, 50, 10, 5, 1 (원)으로 거슬러 주면 된다.

 

Point 1)  가장 적은 잔돈의 개수이기에 가장 큰 거스름돈 단위부터 작은 단위로 먼저 계산해서 거슬러 줘야 한다.

 

위의 포인트는 그리디 알고리즘의 핵심으로 단계적으로 문제를 분할하였을 때 최적의 선택을 한 경우 정답이면, 이는 그리디 알고리즘이다.

 

    if cost>=value:
        result+=cost//value
        cost-=value*(cost//value)

 

result는 동전 개수 cost는 1000에서 입력값을 뺀 후의 거슬러줘야 하는 금액이다. value는 500원 100원 과 같은 비교해야 하는 금액이다.

위의 if문은 반복되기 때문에 함수로 처리해 주었다.

 

for ele in [500,100,50,10,5,1]:calculate(ele)

 

이 함수의 매개변수인 value는 500,100, 50, 10, 5, 1 (원)으로 이것도 함수호출이 반복됨으로써 for문으로 처리해 주었다.