[Node.js] 백준 1463: 1로 만들기

문제 요약

백준 1463: 1로 만들기

• 정수 X에 사용할 수 있는 연산은,

1. X가 3으로 나누어 떨어지면, 3으로 나눈다.
2. X가 2로 나누어 떨어지면, 2로 나눈다.
3. 1을 뺀다.

• 이 세 가지를 적절히 조합한 횟수의 최솟값을 출력한다.
  
  
  입력

//입력 1
2
//입력 2
10

출력

//출력 1
1
//출력
3

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

const dp = Array.from({ length: count + 1 }, () => 0);

for (let i = 2; i < dp.length; i++) {
  dp[i] = dp[i - 1] + 1;

  if (i % 3 === 0) {
    dp[i] = Math.min(dp[i], dp[i / 3] + 1);
  }

  if (i % 2 == 0) {
    dp[i] = Math.min(dp[i], dp[i / 2] + 1);
  }
}
console.log(dp[count]);

중요 개념

• 숫자 2와 3은 1로 가는 경우의 수가 한 가지이다.
• 숫자 4는 3으로 가는 경우의 수 + 3이 1로 가는 경우의 수의 합
• 숫자 5는 4로 가는 경우의 수 + 4가 1로 가는 경우의 수의 합
• 숫자 6은 5로 가는 경우의 수 + 5가 1로 가는 경우의 수

dp[x] = dp[x-1] + 1;

이를 점화식으로 나타내면 아래와 같다. 경우의 수를 카운트하는 식인 것이다.

0,1 나누어도 카운트가 0이니 제외하므로 i는 2부터 시작된다.

다음 Math.min()을 이용해 최솟값을 비교한다.