문제

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

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

N에서 1,2,3 연산을 최소로 사용해 1로 만드는 방법을 찾는 문제이다.
예제 입력에서 10의 경우에는 10 → 9 → 3 → 1 로 3번만에 갈 수 있다.