시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 1024 MB234794482741.683%

문제

마법소녀인 마도카는 너무나도 고양이를 좋아하는 나머지 마법을 이용하여 고양이 $N$마리를 집에서 키우기로 결심했다!

마도카는 한 번의 행동에서 다음 $2$가지 마법 중 하나를 선택하여 사용한다. 처음에는 마도카의 집에 고양이가 존재하지 않는다.

  • 생성 마법: 고양이 $1$마리를 마도카의 집에 생성한다.
  • 복제 마법: 마도카의 집에 있는 고양이 일부 또는 전부를 대상으로 하여 복제한다. 즉, 만약 현재 마도카의 집에 고양이가 $k$마리 존재한다면, $0$마리 이상 $k$마리 이하의 고양이를 마도카의 집에 추가할 수 있다.

마도카는 위의 $2$가지 마법을 적절히 사용하여, 최소의 행동 횟수로 마도카의 집에 정확히 $N$마리의 고양이가 있도록 만들고 싶다. 계산을 어려워하는 마도카를 위해 최소의 행동 횟수를 계산해주자!

입력

첫 번째 줄에 키우기를 원하는 고양이의 수 $N(0\leq N\leq 10^{12})$이 정수로 주어진다.

출력

첫 번째 줄에 정확히 $N$마리의 고양이를 마도카의 집에 들일 수 있는 최소의 행동 횟수를 출력한다.

예제 입력 1

1

예제 출력 1

1

예제 입력 2

6

예제 출력 2

4

올바른 행동 순서가 될 수 있는 하나의 예시는 아래와 같으며, $4$번보다 더 작은 행동 횟수로 $6$마리의 고양이를 마도카의 집에 들이는 것은 불가능하다.

  • 초기 상태($0$마리) $\rightarrow$ 생성 마법($1$마리) $\rightarrow$ 생성 마법($2$마리) $\rightarrow$ 복제 마법($4$마리) $\rightarrow$ 복제 마법($6$마리)

예제 입력 3

2147483648

예제 출력 3

32

원하는 고양이의 수가 $32$bit 정수형 범위를 벗어날 수 있음을 주의하라.

출처

Contest > BOJ User Contest > 와쿠(AGCU)컵 > 제1회 와쿠(AGCU)컵 C번