시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 307 47 26 13.904%

문제

1부터 시작해서 N을 만드려고 한다. 사용할 수 있는 연산은 아래와 같이 총 3가지이다. 이 때, N을 만드는데 사용하는 연산의 최소 횟수를 구하는 프로그램을 작성하시오.

  1. 현재 수를 1 증가시킴 (현재 수+1)
  2. 현재 수가 1보다 크면 1 감소 시킴 (현재 수-1)
  3. 현재 수를 자연수 제곱함. (현재 수^x, x는 자연수)

입력

첫째 줄에 N이 주어진다. N은 10^18보다 작거나 같은 자연수이다.

출력

첫째 줄에 문제의 정답을 출력한다.

예제 입력

80

예제 출력

4

힌트

출처

  • 어색한 표현을 찾은 사람: 79brue
  • 문제를 번역한 사람: baekjoon