[백준] 14916번 : 거스름

문제

https://www.acmicpc.net/problem/14916

춘향이는 편의점 카운터에서 일한다.

손님이 2원짜리와 5원짜리로만 거스름돈을 달라고 한다. 2원짜리 동전과 5원짜리 동전은 무한정 많이 가지고 있다. 동전의 개수가 최소가 되도록 거슬러 주어야 한다. 거스름돈이 n인 경우, 최소 동전의 개수가 몇 개인지 알려주는 프로그램을 작성하시오.

예를 들어, 거스름돈이 15원이면 5원짜리 3개를, 거스름돈이 14원이면 5원짜리 2개와 2원짜리 2개로 총 4개를, 거스름돈이 13원이면 5원짜리 1개와 2원짜리 4개로 총 5개를 주어야 동전의 개수가 최소가 된다.

입력

첫째 줄에 거스름돈 액수 n(1 ≤ n ≤ 100,000)이 주어진다.

출력

거스름돈 동전의 최소 개수를 출력한다. 만약 거슬러 줄 수 없으면 -1을 출력한다.

첫 시도

const fs = require("fs");
let input = parseInt(fs.readFileSync("/dev/stdin").toString().trim());

let result = 0;

if (input == 1 || input == 3) {
  console.log(-1)
} else {
  while (input > 0) {
    if (parseInt(input / 5)) {
      if (input % 5 == 0 || input % 5 > 4) {
        input = input - 5;
        result += 1;
      } else {
        input = input - 2;
        result += 1;
      }
    } else {
      input = input - 2;
      result += 1;
    }
  }

  console.log(result)

}

당연히 2원과 5원으로 최소 개수의 거스름돈을 만들어내야 하니, 5원을 재빨리 탕진해야겠다고 생각했다. 그렇게 while문을 돌리면서 5원을 먼저 빼고, 5원의 예외상황이 생기는 곳에서 2원을 빼주면서 값을 도출했다.

하지만 불필요한 반복 연산이 생기면서 시간은 184ms가 소요되었다.

두번째 시도

const fs = require("fs");
let input = parseInt(fs.readFileSync("/dev/stdin").toString().trim());

let result = 0;

if (input === 1 || input === 3 ) {
    console.log(-1)
} else {
    const quotient = parseInt(input/5);
    const remainder = input%5;
    
    if(remainder === 3) {
        console.log(quotient + 3)
    } else if (remainder === 1) {
        console.log(quotient + 2)
    } else if (remainder%2 === 0) {
        console.log(quotient + remainder/2)
    } else {
        console.log(quotient)
    }
}

생각해보니 굳이 하나씩 빼가며 반복 연산을 할 필요가 있나 싶었다. 그냥 5로 먼저 나누고, 예외 상황을 고려하는 것이 더 빠를 것 같다고 생각했다. 그리하여 5를 먼저 나눠버리고, 나머지가 홀수 / 짝수인 경우를 고려하였다.

최종 리팩토링 버전

const fs = require("fs");
let input = parseInt(fs.readFileSync("/dev/stdin").toString().trim());

if (input == 1 || input == 3) {
  console.log(-1)
}  else {
    if ((input%5)%2 === 0) {
        console.log(parseInt(input/5) + (input%5)/2)
    } else {
        console.log(parseInt(input/5) + parseInt((input%5)/2)+2 )
    }
}

2번째 버전을 좀 더 간결하게 작성한 것이다. 5로 나눈 나머지가 홀수 짝수인 경우에 나름의 규칙성을 찾아서 다음과 같이 작성하였다. 최종 소요 시간은 128ms였다.

회고

• return 문은 함수 scope 안에서만 사용할 수 있다. 그러므로 early return은 사실상 함수를 만들지 않는 이상 사용할 수 없으므로 if / else 구문으로 상황을 나누어야 한다.

• javascript에서는 python의 //(몫) 기능이 없고 대신 parseInt()나 Math.ceil()를 통해 몫을 구할 수 있다.

• 내가 생각하기엔 코드를 아무리 간결하게 적는다고 하더라도, 변수를 알맞게 선언하여 재연산을 줄이는 것이 좋은 것 같다.

• 영어로 몫은 quotient, 나머지는 remainder이다.

• 아침 8시에 기상스터디를 하는데, 한 문제씩 풀고 이렇게 velog에 정리해야겠다.