문제

타로는 자주 JOI잡화점에서 물건을 산다. JOI잡화점에는 잔돈으로 500엔, 100엔, 50엔, 10엔, 5엔, 1엔이 충분히 있고, 언제나 거스름돈 개수가 가장 적게 잔돈을 준다. 타로가 JOI잡화점에서 물건을 사고 카운터에서 1000엔 지폐를 한장 냈을 때, 받을 잔돈에 포함된 잔돈의 개수를 구하는 프로그램을 작성하시오.

입력

• 1 < 타로가 지불할 돈 < 1000

380

출력

잔돈에 포함된 매수를 출력하시오.

4

문제 풀이

가장 큰 단위 동전부터 가능한 만큼 최대한 사용하고, 남은 금액을 다시 큰 순서대로 처리합니다. 즉, 가장 큰 동전부터 차레로 거슬러 주는 그리디 전략을 사용합니다.

const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().trim();

let charge = 1000 - Number(input);
let coins = [500, 100, 50, 10, 5, 1];
let count = 0;

for(let coin of coins){
		let temp = Math.floor(charge / coin);
    count += temp;
    charge -= coin * temp;
}

console.log(count);