1로 만들기 3
면접 대비시간 제한0.5초메모리 제한1024 MB
N이 최대 10^18일 때, 3으로 나누기, 2로 나누기, 1 빼기 연산으로 N을 1로 만드는 최소 연산 횟수를 구합니다.
문제
정수 에 사용할 수 있는 연산은 다음 세 가지이다.
- 가 3으로 나누어 떨어지면, 3으로 나눈다.
- 가 2로 나누어 떨어지면, 2로 나눈다.
- 1을 뺀다.
정수 이 주어졌을 때, 위의 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.
입력
첫째 줄에 1보다 크거나 같고, 보다 작거나 같은 정수 이 주어진다.
출력
첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다.
힌트
10의 경우에는 10 → 9 → 3 → 1 순서로 3번 만에 1을 만들 수 있다.