섬

시간 제한1초메모리 제한1024 MB

요약

피보나치처럼 늘어나는 규칙으로 섬마다 참가자가 사라질 때, N번째 참가자가 사라지는 섬 번호를 구한다.

난이도: 쉬움10점 중 3점
유형: 수학, 시뮬레이션, 구현
정답자: 아직 제출이 없습니다

문제

2020년 국제정보올림피아드(IOI)가 싱가포르에서 열린다. 싱가포르는 면적으로는 작지만 많은 섬으로 이루어진 나라다. IOI 일정 중 하나로 $N$ 명의 참가자가 이 섬들을 방문한다. 그런데 참가자들은 피보나치 힙을 어떻게 구현할지 생각하느라 정신이 팔려, 한 명씩 길을 잃고 돌아오지 못한다.

첫 번째 섬에서 참가자 한 명이 사라지고, 두 번째 섬에서 또 한 명이 사라진다. 그다음 섬부터는 바로 앞 두 섬에서 사라진 참가자 수의 합만큼 참가자가 사라진다(그 전에 참가자가 모두 없어지지 않는다면).

마지막 참가자는 몇 번째 섬에서 사라지는가?

입력

첫째 줄에 정수 $N$ 이 주어진다. $1\le N \le 10\,000$ 이며, $N$ 은 참가자의 수다.

출력

정수 $A$ 를 출력한다. $A$ 는 $N$ 번째 참가자가 사라지는 섬의 번호다.

힌트

그림 1. 이 그림은 첫 번째 예제에서 마지막(열두 번째) 참가자가 5번 섬에서 사라진 상황을 나타낸다.

예제3

예제 1
입력
```
12
```
예상 출력
```
5
```
예제 2
입력
```
13
```
예상 출력
```
6
```
예제 3
입력
```
32
```
예상 출력
```
7
```