문제
타로는 자주 JOI잡화점에서 물건을 산다. JOI잡화점에는 잔돈으로 500엔, 100엔, 50엔, 10엔, 5엔, 1엔이 충분히 있고, 언제나 거스름돈 개수가 가장 적게 잔돈을 준다. 타로가 JOI잡화점에서 물건을 사고 카운터에서 1000엔 지폐를 한장 냈을 때, 받을 잔돈에 포함된 잔돈의 개수를 구하는 프로그램을 작성하시오.
입력
입력은 한줄로 이루어져있고, 타로가 지불할 돈(1 이상 1000미만의 정수) 1개가 쓰여져있다.
출력
제출할 출력 파일은 1행으로만 되어 있다. 잔돈에 포함된 매수를 출력하시오.
예제 입력 1
380예제 출력 1
4예제 입력 2
1예제 출력 2
15문제풀이
💡 문제풀이 과정
- 가장 큰 화폐 단위부터 돈을 거슬러 주는 것이 최적의 해이다.
- Why? 큰 화폐 단위의 돈이 항상 작은 화폐 단위의 배수이므로 가능하다.
- 만약 800원을 거슬러 줘야하는데 화폐 단위가 500원, 400원, 100원이라면? 이 경우엔 큰 단위 화폐가 작은 단위 화폐의 배수가 아니다.
- 가장 큰 화폐 단위인 500원을 주면, 500원(1개) + 100원(3개) = 총 4개의 잔돈을 거슬러줘야 한다.
- 하지만, 400원 짜리로 거슬러 준다면, 2개만 주면 된다.
- 따라서 문제에서 거스름돈의 타입은 제일 큰 500엔부터 내림차순으로 배열을 만든다.
- 잔돈 개수를 셀 count 변수는 거슬러 줄 금액에서 화폐 단위를 나눈 값의 몫(소수점 자리는 버림)을 누적하여 더해나간다.
- 거슬러 줄 금액은 거스름돈을 화폐 단위를 나눈 값의 나머지로 감액하여 나간다.
✅ 답안
const filePath = process.platform === 'linux' ? '/dev/stdin' : '../input.txt';
const price = Number(require('fs').readFileSync(filePath).toString());
const types = [500, 100, 50, 10, 5, 1];
let change = 1000 - price;
let cnt = 0;
for (const i of types) {
cnt += Math.floor(change / i);
change %= i;
}
console.log(cnt);