수 만들기
시간 제한2초메모리 제한128 MB
1에서 시작해 1더하기, 1빼기, 거듭제곱 연산만으로 최대 10^18인 N을 만드는 최소 연산 횟수를 구하는 문제입니다.
문제
처음 수는 1이다. 세 가지 연산을 원하는 순서로 사용해서 수 N을 만들려고 한다. 가능한 연산은 다음과 같다.
- 현재 수에 1을 더한다.
- 현재 수가 1보다 크면 현재 수에서 1을 뺀다.
- 자연수 x를 하나 골라 현재 수를 현재 수^x로 바꾼다.
N을 만들기 위해 필요한 연산 횟수의 최솟값을 구하라.
입력
첫째 줄에 자연수 N이 주어진다. N은 10^18 이하이다.
출력
첫째 줄에 필요한 최소 연산 횟수를 출력한다.