시간 제한 메모리 제한 제출 횟수 정답 횟수 (비율) 정답자 수
5.0 초 512 MB 1779 665 (37%) 563
문제
태양이는 숫자 $N$을 가지고있는데, 그 수를 $1$로 만들고싶다. 각 단계에서 태양이가 할 수 있는 행동은 다음 중 하나이다. 1. $N$이 $3$으로 나누어 떨어지면, $3$으로 나눈다. 2. $N$이 $2$로 나누어 떨어지면, $2$로 나눈다. 3. $1$을 뺀다. 태양이는 게으르기 때문에, 행동의 횟수를 최소화하고자 한다. N이 입력으로 들어올 때, $1$이 되기 위한 최소 행동수를 구하여라.
입력
첫째줄에 태양이가 가진 수 $N(1 \le N \le 1,000,000)$이 주어진다.
출력
첫째줄에 $1$이 되기 위한 최소 행동 수를 출력한다.
힌트
#### 입력 예제 ``` 10 ``` #### 출력 예제 ``` 3 ``` #### 예제 해설 $10 \rightarrow 9 \rightarrow 3 \rightarrow 1$