[백준 2201] 이친수 찾기

문제 링크 => 2201번: 이친수 찾기 (acmicpc.net)

2201번: 이친수 찾기

---

다이나믹 프로그래밍 문제이다.

 

이친수는 다음과 같은 성질을 갖는다고 한다.

1. 이친수는 0으로 시작하지 않는다.
2. 이친수에서는 1이 두 번 연속으로 나타나지 않는다. 즉, 11을 부분 문자열로 갖지 않는다.

예를 들어서 1, 10, 100, 101, 1000, 1001, 1010, 10000, ... 와 같은 숫자들이 이친수이다.

 

그렇다면 이 숫자들을 나열하여 규칙성을 찾아보면 다음과 같은 규칙이 나온다는것을 확인할 수 있다.

 

1 => m[1]=1

10 => m[2]=2

100 => m[3]=3

101

1000 => m[4]=5

1001

1010

10000 => m[5]=8

10001

10010

10100

10101

100000 => m[6]=13

 

맨 앞자리가 1이고 나머지 숫자가 전부 0일 때 몇번째인지를 판단해 보면 m[x] = m[x-1] + m[x-2]; 식이 나온다.

 

즉, 피보나치 수열을 통해 맨 앞자리가 1이고 나머지 숫자가 전부 0일때 몇번째 숫자인지를 확인 가능하다.

 

그렇다면 m[x]를 통해 어떻게 숫자를 찾아낼 수 있을까? 이 규칙은 다음과 같다.

 

예를들어서 10101 을 살펴보도록 하면, m[5] + m[3] + m[1] = 12 번째 숫자이다.

 

이를 역으로 접근해야 하므로 다음과 같은 방법으로 찾아줘야 한다.

1. 처음으로 m[x] < k < m[x+1] 를 만족하도록 하는 x를 찾는다.
2. k = k - m[x] 를 해준다.
3. k > 0 인 경우 1번으로 돌아가고 0인 경우 반복을 멈춘다.

풀이 code

#define _CRT_SECURE_NO_WARNINGS
#include <string>
#include <stdio.h>
#include <math.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <time.h>
#define INF 100000000
#define endl '\n'
#define MOD 1000000009
#define ll long long

using namespace std;

ll k;
ll memo[88];

void dp() {
	memo[1] = 1, memo[2] = 2, memo[3] = 3;
	for (ll idx = 4; memo[idx-1] < 1000000000000000000; idx++) {
		memo[idx] = memo[idx - 1] + memo[idx - 2];
	}
}

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

	dp();
	cin >> k;
	int maxNum = 0;
	map<int, int> m;
	while (k != 0) {
		int idx;
		for (int i = 1; i <= 87; i++) {
			if (memo[i] > k) {
				idx = i - 1;
				maxNum = max(maxNum, idx);
				k -= memo[idx];
				break;
			}
		}
		m[idx]++;
	}

	for (int i = maxNum; i >= 1; i--) {
		if (m[i]) cout << 1;
		else cout << 0;
	}

	return 0;
}