문제

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

손님이 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을 출력한다.

예제 입력 1

13

예제 출력 1

5

예제 입력 2

14

예제 출력 2

4

나의 코드

const input = Number(require("fs").readFileSync("/dev/stdin").toString().trim());
const INF = Number.POSITIVE_INFINITY;

let dp = [0, INF];
for (let i = 2; i <= input; i++) {
  if (i === 2 || i === 5) {
    dp[i] = 1;
    continue;
  }
  const fiveBefore = dp[i - 5] || INF;
  const twoBefore = dp[i - 2] || INF;
  dp[i] = Math.min(fiveBefore, twoBefore) + 1;
}
const ans = dp[input];
console.log(ans === INF ? -1 : ans);

처음으로 Infinity를 사용하여 풀어봤다.
dp 테이블에서 특정 숫자의 답을 계산해봤을 때 dp[i-2]에 2를 더하거나 dp[i-5]에 5를 더한 값이 답이 될 수 있다. 문제에서는 최솟값을 구하라고 했으니 dp[i-2]와 dp[i-5] 둘 중 더 작은 값 + 1이 답이 된다. 다만, dp[i-2]나 dp[i-5]가 0보다 작거나, 거슬러줄 수 없는 값일 때는 Math.min을 사용하더라도 더 작은 값이 답이 될 수가 없다. 따라서 의도적으로 거슬러줄 수 없는 값일 때는 Infinity 값을 임시로 할당했다.
그리고 5의 경우에는 예외적으로 dp[i-2]는 INF이고 dp[i-5]는 0이기 때문에 fiveBefore과 twoBefore이 둘 다 무한대가 되어 의도한 값이 반환되지 않는다. 2도 마찬가지이다. 따라서 2와 5의 경우에는 for문을 시작할 때 바로 1을 할당하여 예외처리를 해주었다.

문제에서 제시한대로 불가능한 값에 -1을 할당할 경우 아래 대소비교가 꼬여버린다면 Infinity를 적극 활용해보자 ㅎㅎㅎ 화이팅!!!