문제

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

X가 3으로 나누어 떨어지면, 3으로 나눈다.
X가 2로 나누어 떨어지면, 2로 나눈다.
1을 뺀다.
정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.

입력

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

출력

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

문제 접근

3으로 나눌 수 있으면 dp[i] = dp[i / 3] + 1
2로 나눌 수 있으면 dp[i] = dp[i / 2] + 1
1을 뺄 수 있으면 dp[i] = dp[i - 1] + 1

dp 배열을 만들고, 위 경우에서 제일 낮은 값을 dp 배열에 할당시킨다.

➡️ 정수 i를 1로 만드는 데 필요한 최소 연산 횟수

단, 1을 나눌 때에는 값이 필요없으므로 연산도 없다. 따라서 dp[1] = 0

정답

const fs = require('fs');
const N = Number(fs.readFileSync(0, 'utf8').trim());

// 0으로 채운 dp 배열 생성
const dp = new Array(N + 1).fill(0);
// dp[1]은 연산횟수 0
dp[1] = 0;

// 2부터 시작한다.
for (let x = 2; x <= N; x++) {
  dp[x] = dp[x - 1] + 1; // 1을 뺄 수 있는 경우
  if (x % 2 === 0) dp[x] = Math.min(dp[x], dp[Math.floor(x / 2)] + 1); // 2로 딱 나누어 떨어지는 경우. 1을 만들어야하기 때문에 마지막에 +1 ♥️ 여기서 dp[x]가 최소수로 업데이트 된다.
  if (x % 3 === 0) dp[x] = Math.min(dp[x], dp[Math.floor(x / 3)] + 1); // 3으로 딱 나누어 떨어지는 경우. 1을 만들어야하기 때문에 마지막에 +1 ♥️ 여기서 dp[x]가 위에서 2로 나눈 값과 비교하여 최소수로 업데이트 된다.
}

console.log(dp[N]);

왜 이렇게 작성하는가?

1. 1을 빼는 연산은 항상 가능하므로 dp[x]의 합리적인 상한선을 먼저 잡아 둡니다. 이는 “최소 한 번은 1을 빼면 x에 도달할 수 있다”는 보장
2. 2 또는 3으로 나누는 연산은 x가 나누어떨어질 때만 가능하므로, 조건을 통과할 때만 후보로 비교하여 더 작은 값이면 갱신.
3. 이 패턴을 쓰면 별도의 초기값을 Infinity로 둘 필요가 없고, 불가능한 연산 후보를 억지로 비교할 필요도 없어 간결하고 안전함.

작은 것 부터 큰 것으로. DP 접근
기본값 설정 → 조건부 최소 갱신 흐름

예시로 N이 6이라면 for문에서는 2부터 6까지의 dp 배열에 값이 들어갈 것임.

동작 예시

N = 6

• 초기 설정: dp = dp[6 - 1] + 1
• 6 % 2 === 0 이므로 dp = Math.min(dp, dp + 1)로 갱신 가능
• 6 % 3 === 0 이므로 3으로 나누어짐. 6 % 2 === 0에서 나눈 값이 업데이트된 dp[x]와 비교하여 최소수 업데이트 진행된다.