1로 만들기
면접 대비시간 제한0.15초메모리 제한128 MB
N을 1로 만들기 위해 3으로 나누기, 2로 나누기, 1 빼기 연산을 최소 몇 번 사용해야 하는지 구합니다.
문제
정수 X에 대해 다음 세 가지 연산을 사용할 수 있다.
- X가 3으로 나누어떨어지면 X를 3으로 나눈다.
- X가 2로 나누어떨어지면 X를 2로 나눈다.
- X에서 1을 뺀다.
정수 N이 주어질 때, 위 연산들을 적절히 사용해 N을 1로 만들려고 한다. 필요한 연산 횟수의 최솟값을 구하라.
입력
첫째 줄에 정수 N이 주어진다. (1 <= N <= 1,000,000)
출력
첫째 줄에 필요한 연산 횟수의 최솟값을 출력한다.
힌트
N = 10이면 10 -> 9 -> 3 -> 1 순서로 3번의 연산만에 1을 만들 수 있다.