시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 52 6 6 85.714%

문제

x의 P승을(1 <= P <= 20,000) 최대한 빠르게 계산하고자 한다. 그런데 계산결과가 굉장히 크므로 여기서는 계산 도중 값을 저장하는 데 있어 두 개의 변수만을 사용한다.

두 변수 중 하나는 x로, 다른 하나는 1로 초기화되어 있다. 우리가 쓸 수 있는 연산은, 현재 저장되어 있는 값들을 서로 곱하거나 나누어서 그 결과값을 임의의 변수에 저장하는 것이다. 최종 결과가 저장되는 위치는 아무래도 좋다.

예를 들어 x^9을 계산하고자 할 때, 다음과 같은 방법이 가능하다.

연산 회수 0 1 2 3 4
변수1 x x x x^5 x^9 ☜☜☜
변수2 1 x^2 x^4 x^4 x^4

P를 입력받아, x^P를 구하기 위한 최소 연산 회수를 구하여라.

입력

첫째 줄에 P가 들어온다.

출력

최소 연산 회수를 출력한다.

예제 입력

31

예제 출력

6

힌트

출처

  • 데이터를 추가한 사람: doju
  • 문제의 오타를 찾은 사람: kcm1700