boj 2201 이친수 찾기

www.acmicpc.net/problem/2201

2201번: 이친수 찾기

 

dp[length] : 길이가 length인 이친수의 시작 번호

 

1. 이친수는 0으로 시작하지 않는다.

2. 이친수에서는 1이 두 번 연속으로 나타나지 않는다. 즉, 11은 이친수가 아니다.

위 조건을 고려하여 길이당 이친수의 갯수는 피보나치 수열로 구할 수 있습니다.

 

저는 이를 이용하여 dp에 각 길이당 시작하는 번호를 담아놓습니다.

dp[1] = 1, dp[2] = 2, dp[3]= 3, dp[4] = 5, dp[5]=8, dp[6] = 13, ... 이런식으로 되고,

 

그리고 입력받은 N의 길이를 구합니다.

길이가 i일 때의 시작번호와 비교를 하여 dp[i] > N이면 length는 i - 1입니다.

 

그리고 length만큼 반복문을 돌려주면서 두 가지의 경우를 확인합니다.

1. dp[length] <= N이면 (번호 N이 length의 시작점보다 뒤에 있으면)

 => 1을 출력하고 N을 N의 시작번호만큼 빼줍니다.

 

2. dp[length] > N이면 (번호 N이 length의 시작점보다 앞에 있으면)

 => 0을 출력합니다.

 

 

#include <iostream>
using namespace std;
typedef long long ll;
 
ll dp[91], N;
 
void init() {
    dp[1] = 1;
    dp[2] = 2;
    for (int i = 3; i <= 90; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
}
 
void solve() {
    int length = 0;
    for (int i = 1; i <= 90; i++) {
        if (dp[i] > N) {
            length = i - 1;
            break;
        }
    }
 
    while (length) {
        if (dp[length] <= N) {
            cout << 1;
            N -= dp[length];
        }
        else {
            cout << 0;
        }
        length--;
    }
    cout << '\n';
}
 
void input() {
    cin >> N;
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    init();
    input();
    solve();
 
    return 0;
}