백준 2201번, 이친수 찾기 풀이

문제

백준 2201번

풀이

길이가 $ 1, 2, 3, 4, 5 $인 이친수들을 모두 적어보겠습니다.

$ 1 $

$ 10 $

$ 100, 101 $

$ 1000, 1001, 1010 $

$ 10000, 10001, 10010, 10100, 10101 $

이며 각각의 개수는 $ 1, 1, 2, 3, 5 $와 같습니다.

 

대충 규칙이 피보나치 수열과 같다는 것을 볼 수 있습니다.

 

길이가 $K$인 이친수의 개수가 피보나치 수열의 원소와 같다는 믿음을 가지면 아래 문제를 푸는 것으로 바꿀 수 있습니다.

$N$번째 이친수의 길이는 몇인가?

이는 피보나치 수열을 한번 돌리면 길이를 구할 수 있습니다.

 

다음은, 길이가 $ K ( K \geq 2) $인 경우 이친수는 "항상" 앞이 10으로 시작합니다. (이친수의 시작은 항상 1이므로, 두번째 자리까지 0으로 결정되기 때문)

그러면, 앞에 10을 채워두고 뒤에 $ K - 2 $를 채우면 됩니다.

 

길이가 $ K $인 이친수들의 3번째부터 $K$번째까지는 길이가 1부터 $ K - 2 $까지의 2친수들로 채워져 있습니다.

(자릿수가 모자라면 0으로 채워줌)

실제로 위와 같이 그림이 그려지게 됩니다. 따라서, 해야할 일은 길이가 $K$인 이친수 중에 $i$번째라면, $i$번째 이친수를 찾는 문제로 변형할 수 있습니다.

 

즉 분할 정복 문제로 보고 풀 수 있습니다.

소스코드

#include <bits/stdc++.h>

#define all(v) v.begin(), v.end()

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpii;
typedef vector<pll> vpll;
typedef unordered_map<int, int> mpii;

vpll dp(91);

auto digit(ll k) { //k번째 이친수의 자릿수
	return lower_bound(all(dp), pll(k, -1))->second;
}

auto cnt(ll k) { //길이가 k인 이친수의 개수
	return (--lower_bound(all(dp), pll(k, -1)))->first;
}

string solve(ll k) {
	if (!k) return "";
	if (k == 1) return "1";
    //i번째 이친수의 길이가 k - 2보다 작다면 앞을 0으로 채워줌
	ll diff = digit(k) - 2 - digit(k - cnt(k) - 1);
	string ret = "10";
	while (diff--) ret += "0";
    //k번째 이친수 중에서 i번째이면, i번째 이친수를 계속 찾아 줌
	return ret + solve(k - cnt(k) - 1);
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

	dp[1].first = dp[1].second = dp[2].first = 1;
	for (ll i = 3; i <= 90; i++) dp[i].first = dp[i - 1].first + dp[i - 2].first;
	for (ll i = 2; i <= 90; i++) dp[i].first += dp[i - 1].first, dp[i].second = i;

	ll k; cin >> k;
	cout << solve(k);
}