[BOJ 2201 // C++] 이친수 찾기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 2201번 문제인 이친수 찾기이다.
문제는 아래 링크를 확인하자.

https://www.acmicpc.net/problem/2201 

2201번: 이친수 찾기

크기순 k번째 "이친수"를 찾는 문제이다. 이는 각 이친수에 leading zero를 적절히 붙여 사전순으로 k번째 이친수를 찾는 문제로 바꿔 생각할 수 있다.

 

이번 자리에 0을 쓸 때 뒤를 마저 채워 만들 수 있는 이친수의 개수를 이용해 k번째 이친수를 한 자리씩 구해나가자. 이 과정을 구현할 때 수 0은 문제의 정의 상 이친수에 포함되지 않음에 주의하자. (0은 '0'으로 시작하기 때문이다.) 글쓴이는 k번째 이친수의 첫 자리부터 탐색을 시작하게끔 구현해 위의 귀찮은 구현을 회피하였다.

 

또한, 이친수의 개수와 피보나치 수 사이에 연관성이 있으므로 피보나치 수열의 성질을 이용하면 구현을 더욱 편리하게 할 수 있다.

 

아래는 제출한 소스코드이다.

#include <iostream>
using namespace std;
typedef long long ll;

ll fib[88];
ll K; int N;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	fib[0] = fib[1] = 1;
	for (int i = 2; i < 88; i++) fib[i] = fib[i - 1] + fib[i - 2];

	cin >> K;
	while (fib[N] - 1 < K) N++;
	
	cout << 1;
	K -= fib[N - 1] - 1;
	N--;

	while (N > 1) {
		if (K <= fib[N - 1]) {
			cout << 0;
		}
		else {
			cout << 1;
			K -= fib[N - 1];
		}
		N--;
	}
}