K번째 이친수 찾기
시간 제한2초메모리 제한128 MB
선행 0이 없고 11이 연속으로 나오지 않는 이진수들을 값 순서로 나열했을 때 K번째 수를 구하는 문제입니다.
문제
0과 1로만 이루어진 수를 이진수라고 한다. 그중 다음 조건을 모두 만족하는 수를 이친수라고 한다.
- 0으로 시작하지 않는다.
- 1이 두 번 연속해서 나타나지 않는다. 즉,
11을 부분 문자열로 갖지 않는다.
대표적으로 1, 10, 100, 101, 1000, 1001은 이친수이다. 반대로 0010101은 첫 번째 조건을 만족하지 않고, 101101은 두 번째 조건을 만족하지 않으므로 이친수가 아니다.
모든 이친수를 이진수로 보았을 때의 값이 작은 순서대로 정렬하고, 앞에서부터 1번부터 번호를 붙인다. 자연수 K (1 ≤ K ≤ 1,000,000,000,000,000,000)가 주어질 때, K번째 이친수를 출력하는 프로그램을 작성하시오.
입력
첫째 줄에 자연수 K가 주어진다.
출력
첫째 줄에 K번째 이친수를 출력한다.