Baekjoon 문제 풀기 (5585번 : 거스름돈) Python

5585번 : 거스름돈

1. 문제읽기

---

대표적인 그리디 알고리즘 거스름돈 문제

그리디 알고리즘하면 제일 먼저 생각나는 거스름돈 문제이다!
어떻게 푸는지는 감으로 아는데 정확한 풀이가 기억나지 않았다.
맞추긴 했지만 더러운 코드였다. ㅋㅋ

2. 제출 코드

---

m = 1000-int(input())
count = 0

while m != 0:
    if m >= 500:  # 500원X1 거슬러주기
        count += 1
        m -= 500
    elif m >= 100:  # 100<=m<500 100원 1, 2, 3, 4개
        count += m//100
        m -= (m//100)*100
    elif m >= 50:  # 50<=m<100 50원X1
        count += 1
        m -= 50
    elif m >= 10:  # 10<=m<50 10원 1, 2, 3, 4개
        count += m // 10
        m -= (m // 10) * 10
    elif m >= 5:  # 5<=m<10 5원X1
        count += 1
        m -= 5
    elif m >= 1:  # 1<=m<5
        count += m // 1
        m -= (m // 1)

print(count)

3. 공부할 것

---

몫이 있으면 나머지도 있는 법!!!
나머지를 사용해서 풀면 더 깔끔하게 풀 수있다.
리스트도 사용할 수 있다…

380%100을 하면 100만 나눈 280이 나오는 줄 알았는데 당연히 80이 나온다.
그래서 아래와 같은 m = m % i 의 식을 사용할 수 있다.
멍청했다…
코드를 다듬어보면 아래와 같다.

m = 1000-int(input())
count = 0

arr = [500, 100, 50, 10, 5, 1]

for i in arr:
    count += m//i
    m = m%i

print(count)