[백준/파이썬] 5585번 거스름돈 풀이

---

• 백준 문제풀이 전체 목록 보기

---

문제 정보

• 문제 출처: 백준 온라인 저지
• 문제 링크: 5585번 거스름돈
• 문제풀이 코드 GitHub 링크
• 제출 언어: Python 3

풀이

문제

1000엔 지불 후 거슬러줘야 할 금액에 대해 동전 개수의 최솟값을 구하는 문제입니다.

코드

n = 1000-int(input())

cnt = n // 500
n%=500
cnt += n // 100
n%=100
cnt += n // 50
n%=50
cnt += n // 10
n%=10
cnt += n // 5
n%=5
cnt += n // 1
n%=1


print(cnt)

설명

가치가 큰 동전부터 차례로 사용하는 그리디 방식으로 각 동전 사용 개수를 누적하면 최솟값이 됩니다.

---

• 백준 문제풀이 전체 목록 보기

---