cho.sh

수 만들기

1에서 시작해 1더하기, 1빼기, 거듭제곱 연산만으로 최대 10^18인 N을 만드는 최소 연산 횟수를 구하는 문제입니다.

어려움8정수론수학재귀백트래킹아직 제출이 없습니다시간 제한2초메모리 제한128 MB

문제

처음 수는 1이다. 세 가지 연산을 원하는 순서로 사용해서 수 N을 만들려고 한다. 가능한 연산은 다음과 같다.

  1. 현재 수에 1을 더한다.
  2. 현재 수가 1보다 크면 현재 수에서 1을 뺀다.
  3. 자연수 x를 하나 골라 현재 수를 현재 수^x로 바꾼다.

N을 만들기 위해 필요한 연산 횟수의 최솟값을 구하라.

입력

첫째 줄에 자연수 N이 주어진다. N은 10^18 이하이다.

출력

첫째 줄에 필요한 최소 연산 횟수를 출력한다.