문제

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

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

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

입력

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

출력

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

예제

예제 입력 1

1
2
2

예제 출력 1

1
2
1

예제 입력 2

1
2
10

예제 출력 2

1
3

내 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
const input = +require("fs").readFileSync("/dev/stdin").toString().trim();

const DP = [];
DP[1] = 0;

for (let i = 2; i <= input; i++) {
  const availables = [DP[i - 1]];
  if (i % 2 === 0) {
    availables.push(DP[Math.floor(i / 2)]);
  }
  if (i % 3 === 0) {
    availables.push(DP[Math.floor(i / 3)]);
  }

  DP[i] = 1 + Math.min(...availables);
}

console.log(DP[input]);

DP는 작은 문제부터 해결하여 이를 저장하여 큰 문제를 해결하는 프로그래밍 방식이다.

  1. 자연수 2부터 N까지 수가 주어진 3가지 연산으로 1을 만들 수 있는 최소한의 연산 횟수를 담은 배열 DP를 생성한다.
  2. 예를 들어 숫자 2는 1을 만들 수 있는 연산횟수가 1회이므로 DP[2] = 1 이다. 그렇다면 DP[6]는 어떻게 알 수 있는가? 바로 숫자 6을 3가지 연산을 수행한 결과값(5,2,3)을 DP 배열에서 찾고 1을 더해주면 된다. DP[6] = 1 + (DP[2], DP[3], DP[5] 중 최솟값)

나는 중간에 2로 나눴을 때와 3으로 나눴을 때를 else if로 하는 바람에 2로 나눠지면 3으로는 못나누도록 코드를 짜서 계속 틀렸다고 나왔었다.