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

문제

정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.

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

정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.

입력

첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다.

출력

첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다.

예제 입력 1

2

예제 출력 1

1

예제 입력 2

10

예제 출력 2

3

힌트

10의 경우에 10 → 9 → 3 → 1 로 3번 만에 만들 수 있다.

---

문제풀이

• const dp = Array(N + 1).fill(0);
  • 1에서 N까지의 모든 수에 대해 최소 연산 횟수를 저장하기 위한 dp 배열 초기화. 1부터 시작하므로, 매핑하기 위해 배열의 길이는 N + 1로 한다.
• for (let i = 2; i <= n; i++) {}
  • N = 1인 경우는 0번 즉, dp[1]의 경우 0이므로, dp[2]부터 값을 구하기 위한 반복문을 설정한다.
• dp[i] = dp[i - 1] + 1
  • dp[i]는 숫자 i에 도달하기 위해 필요한 최소 연산 횟수이다. 따라서, 현재 횟수는 이전 횟수에 1을 더한다.
• if (i % 2 === 0) dp[i] = Math.min(dp[i], dp[i / 2] + 1);
  • 현재 수가 2로 나누어 떨어지면, 2로 나눈 수의 최소 횟수에 1을 더한 값과 비교하여 더 작은 값을 갱신한다.
• if (i % 3 === 0) dp[i] = Math.min(dp[i], dp[i / 3] + 1);
  • 현재 수가 3으로 나누어 떨어지면, 3으로 나눈 수의 최소 횟수에 1을 더한 값과 비교하여 더 작은 값을 갱신한다.

✅ 답안

const filePath = process.platform === 'linux' ? '/dev/stdin' : './input.txt';
let n = +require('fs').readFileSync(filePath).toString().trim();

// 다이나믹 프로그래밍을 위한 배열 초기화
const dp = Array(n + 1).fill(0);

// Bottom-up 방식의 다이나믹 프로그래밍 진행
for (let i = 2; i <= n; i++) {
  // 최소 연산 횟수는 이전 수의 최소 횟수에 1을 더한 값으로 초기화
  dp[i] = dp[i - 1] + 1;

  // 현재 수가 2로 나누어 떨어지면, 2로 나눈 수의 최소 횟수에 1을 더한 값과 비교하여 갱신
  if (i % 2 === 0) {
    dp[i] = Math.min(dp[i], dp[i / 2] + 1);
  }

  // 현재 수가 3으로 나누어 떨어지면, 3으로 나눈 수의 최소 횟수에 1을 더한 값과 비교하여 갱신
  if (i % 3 === 0) {
    dp[i] = Math.min(dp[i], dp[i / 3] + 1);
  }
}

// 주어진 수를 1로 만들기 위해 필요한 최소 연산 횟수를 출력
console.log(dp[n]);