Fi-Binary Number (FBN) timer 1s memory 32MB

Fi-binary number 라는 것은 다음과 같이 정의된다.

1. 0 과 1 로 이루어진 수열이다.

2. 맨 앞자리가 0이 될 수는 없다.

3. 수열에서 1이 두 번 이상 연속적으로 나타날 수 없다.

다음은 잘못된 Fi-binary number의 예이다.

01001010001 (맨 앞자리가 0 이므로)

10100110 (1이 두 번 연속으로 나타나므로)

Fi-binary number를 작은 순서부터 나열해 보면 다음과 같다.

1, 10, 100, 101, 1000, 1001, 1010, 10000, 10001, 10010, 10100, 101010 ...

이 문제의 목표는 자연수 n이 주어졌을 때 n번째 Fi-binary number 를 찾는 것이다.