[알고리즘/그리디] 5585 번 : 거스름돈 - python

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

 

소요시간 : 4분

---

• 문제

---

• 설계하기(접근방법) 

1. 지불할 돈을 입력받는다.

2. 거슬러줄 돈 change을 계산한다.

3. coin_list을 선언하여 큰 동전부터 거스를 수 있게 for문을 순회한다.

change에서 i를 나눈것이 몫이다. 그 몫을 coin_cnt에 더해준다.

change에서 i를 나눈 나머지가 다음 change값이다

4. for문 종료 후 coin_cnt 즉 동전의 개수를 출력한다

 

 

---

• 코드(출력)

pay = int(input())
changes = 1000 - pay

coin_list = [500, 100, 50, 10, 5, 1]
coin_cnt = 0
for i in coin_list:
    coin_cnt += changes // i
    changes %= i

print(coin_cnt)

---

• 얻어갈 부분

1. 그리디 알고리즘을 풀 때 풀이법 정당한지 검토할줄 알아야 한다.

즉 가지고 있는 동전 중에서 큰 단위가 항상 작은 단위의 배수이므로

작은 단위의 동전들을 더해서 다른 해가 나올 수 없다