레이팅 미적용설명
현금 인출기에는 \(50000\)원, \(10000\)원, \(5000\)원, \(1000\)원짜리 지폐가 충분히 들어 있다. 손님이 \(W\)원을 뽑으려 하며, \(W\)는 항상 \(1000\)의 배수이다.
인출기가 내어 주는 지폐의 장수를 가장 적게 하려고 할 때, 필요한 지폐의 최소 장수를 출력하여라. 큰 단위부터 최대한 사용하면 장수가 최소가 됨이 알려져 있다.
제약
\(0 \le W \le 10^7\), \(W\)는 \(1000\)의 배수
입력 형식
첫째 줄에 인출 금액 \(W\)가 주어진다. \(W\)는 \(1000\)의 배수이다.
출력 형식
\(W\)원을 내어 주는 데 필요한 지폐의 최소 장수를 한 줄에 출력한다.
예제 1
입력
67000
출력
5
설명
\(67000 = 50000 + 10000 + 5000 + 1000\times2\)이므로 지폐 \(5\)장이 필요하다.
예제 2
입력
6000
출력
2
설명
\(6000 = 5000 + 1000\)이므로 지폐 \(2\)장으로 뽑을 수 있다.
문제 정보
riseoj 작성
출처 Original
태그