블랙 체인

시간 제한0.1초메모리 제한512 MB

요약

n개(최대 10^18)의 고리로 된 사슬에서 몇 개의 고리를 열어야 남은 조각을 조합해 1g부터 ng까지의 모든 무게를 만들 수 있는지 구합니다.

난이도: 어려움10점 중 9점
유형: 그리디, 조합론, 정수론, 이분 탐색
정답자: 아직 제출이 없습니다

문제

n개의 블랙 고리가 일렬로 연결된 체인이 있다. 블랙 고리 하나의 무게는 정확히 1g이다. 이 고리들을 이용해 1g부터 ng까지 모든 무게를 만들려고 한다. 그러려면 고리를 일부 풀어야 하는데, 고리를 푸는 데 힘이 들기 때문에 최소 개수의 고리만 풀고 싶다. 예를 들어 그림 A.1처럼 7개의 고리로 이루어진 블랙 체인이 있다고 하자. 이 체인에서 3번 고리 하나를 풀어 내면 그림 A.2처럼 3번 고리 1개와 두 개의 체인(1~2번 고리가 연결된 체인과 4~7번 고리가 연결된 체인)으로 나뉜다. 이것들을 이용하면 그림 A.3처럼 1g부터 7g까지 모든 무게를 만들 수 있다.

그림 A.1: 길이가 7인 블랙 체인

그림 A.2: 3개로 나뉜 블랙 체인

무게	1g	2g	3g	4g	5g	6g	7g
고리 구성	`[3]`	`[1-2]`	`[3]` `[1-2]`	`[4-7]`	`[3]` `[4-7]`	`[1-2]` `[4-7]`	`[3]` `[1-2]` `[4-7]`

그림 A.3: 1g부터 7g까지 모든 무게를 만드는 고리 구성

n개의 고리가 연결된 체인이 주어졌을 때, 1g부터 ng까지 모든 무게를 만들기 위해 풀어야 하는 고리의 최소 개수를 구하는 프로그램을 작성하시오.

입력

입력은 표준입력을 사용한다. 첫 번째 줄에 블랙 고리의 개수 n (3 ≤ n ≤ 1018)이 주어진다.

출력

출력은 표준출력을 사용한다. 1g부터 ng까지 모든 무게를 만들기 위해 풀어야 하는 고리의 최소 개수를 출력한다.

예제2

예제 1
입력
```
7
```
예상 출력
```
1
```
예제 2
입력
```
20
```
예상 출력
```
2
```