문제

달나라 토끼들이 사용하는 화폐는 동전뿐이다. 동전의 종류는 1원, 2원, 5원, 7원 이렇게 4종류가 있다. 물건을 사고 동전으로 계산을 하는데 동전의 개수가 최소가 되도록 지불하지 않는 것은 불법이다. 예를 들어, 17원을 지불할 때 7원짜리 동전 1개와 5원짜리 동전 2개로 지불해야 합법이고, 7원짜리 동전 2개와 2원짜리 동전 1개, 1원짜리 동전 1개로 지불해도 17원이 되지만, 총 동전의 개수가 4개가 되어 최소 개수가 아니므로 불법이다.

지불 금액을 입력받아 합법이 되는 동전 개수를 출력으로 내어주는 프로그램을 작성해보자.

입력

첫 번째 줄에 달나라 토끼가 지불해야하는 금액 N(0 ≤ N ≤ 100,000)이 주어진다.

출력

첫 번째 줄에 달나라 토끼가 합법적으로 낼 수 있는 동전의 개수를 출력한다.

예제 입력

12

예제 출력

2

내가 했던 풀이 방법

1. N을 7, 5, 2, 1 순으로 나눈 값을 내림한 값을 각각 더해준다. 만약 N이 나누는 수보다 작을 경우에는 해당 수를 무시한다. 나눠줄 때마다 N을 나눈 나머지로 바꿔준다. -> 실패 (불가능한 경우 발생. 예를 들어 17같은 수는 다음과 같은 풀이로는 7원×2 + 2원×1 + 1원×1로 결과가 4가 되지만, 7원을 1개만 줄 경우, 5원 2개로 총 3개로도 거슬러줄 수 있기 때문이다.)

2. DP 배열에 [0, 1, 1, 2, 2, 1, 2, 1]을 저장한다. 해당 값은 각 돈을 거슬러줄 수 있는 최소개수를 의미한다. 0원은 거슬러주지 않아도 되므로 0, 3원은 1원과 2원이 각각 하나씩 필요하므로 2... 계산을 쉽게하기 위해 0원도 포함해준다.

3. 현재 가격에서 -1, -2, -5, -7해준 결과 중 최소 동전의 개수를 찾아 +1을 해준다. 쉽게 말하면, 현재 가격이 30일 때, 29원, 28원, 25원, 23원을 거슬러받는 동전의 개수를 확인하는 것이다. (+1을 해주는 이유는 29원, 28원, 25원, 23원은 1원, 2원, 5원, 7원 중 1개만 추가해주면 되기 때문이다.)

코드

var fs = require('fs');
let N = fs.readFileSync(0, 'utf-8').toString().trim();
N = Number(N);

let dp = [0, 1, 1, 2, 2, 1, 2, 1];
for (let i = 8; i <= N; i++) {
  dp[i] = Math.min(dp[i - 1], dp[i - 2], dp[i - 5], dp[i - 7]) + 1;
}

console.log(dp[N]);

회고

DP에서 계산 쉽게하려고 0번째 index에 null값을 주었는데 그 부분 때문에 99%에서 틀렸습니다를 봤다...null값을 주게되면 N이 1, 2, 5, 7보다 작은 경우가 있을 때 문제가 발생하는 것 같다. VSCode에서는 문제가 없는데 흠...그래도 맞았으니까 다행이다. 물론... 틀려서 다른 풀이를 참고했지만..언제쯤 DP를 잘 풀게 될까