백준 - 5585번 거스름돈 python 문제풀이 [Hellfer]

https://www.acmicpc.net/problem/5585

5585번: 거스름돈

🔷 알고리즘 분류 - 그리디 알고리즘  난이도 - 브론즈 2

그리디 알고리즘(Greedy Algorithm)은 매 순간 최적이라고 생각되는 결정을 하는 방식으로 문제를 해결하는 알고리즘입니다. 

 

이 때문에 그리디 알고리즘은 '탐욕적'이라는 뜻의 '그리디'라는 이름이 붙었습니다. 

 

그리디 알고리즘이 작동하는 기본 원리는 간단합니다. 매 순간 최선의 선택을 하면서 전체 문제의 해결책을 찾아나갑니다. 

 

이 때문에 그리디 알고리즘은 많은 종류의 최적화 문제에 효율적으로 사용될 수 있습니다. 

 

그러나 그리디 알고리즘은 '항상 최적의 해결책을 보장하는가?'라는 중요한 질문에 대한 답이 '아니요'일 수 있다는 점에서 주의할 필요가 있습니다. 

 

그리디 알고리즘은 그 자체로 국소적인 최적해를 찾는 데는 탁월하지만, 이가 반드시 전체적인 최적해를 보장하진 않습니다.

🔶문제 풀이 - 그리디 알고리즘을 이용한 풀이

# 사용자로부터 입력값을 정수형태로 받아 'n'에 저장합니다.
n=int(input())

# 거스름돈의 개수를 저장할 변수 'count'를 0으로 초기화합니다.
count=0

# 1000원에서 사용자가 지불할 금액 'n'을 빼서 거스름돈 'm'을 계산합니다.
m=1000-n

# 동전의 종류를 큰 단위부터 순서대로 확인하며 거스름돈 'm'을 만드는 과정을 반복합니다.
for i in [500,100,50,10,5,1]:
    # 'm'을 현재 동전 'i'로 나눈 몫을 'count'에 더합니다.
    # 이는 'm'을 현재 동전 'i'로 얼마나 나눌 수 있는지, 즉 현재 동전 'i'가 얼마나 필요한지를 나타냅니다.
    count+=m//i
    
    # 'm'을 현재 동전 'i'로 나눈 후의 나머지를 'm'에 저장합니다.
    # 이는 'm'을 현재 동전 'i'로 나눈 후 남은 금액을 나타냅니다.
    m%=i

# 거스름돈의 개수인 'count'를 출력합니다.
print(count)

🔶문제 이해하기

아래와 같이 입력값이 주어졌다고 가정해 보겠습니다.

 

380

 

1. m(1000-n)은 620이 됩니다.

 

2. for문을 수행하면서  현재 동전 i로 나눈 값을 count에 더합니다.

 

3. count는 i값이 500일 때 count+=1, m은 620-500인 120이 됩니다.

 

4. i값이 100일 때 count+=1, m은 120-100인 20이 됩니다.

 

5. 10일 때 count+=2, 따라서 count는 4가 됩니다.

 

6. 아래와 같이 출력값을 출력하고 종료합니다.

 

4