알고리즘 :: 백준 :: DP :: 2201 :: 이친수 찾기

문제

0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 들 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다.
성질 1) 이친수는 0으로 시작하지 않는다.
성질 2) 이친수에서는 1이 두 번 연속으로 나타나지 않는다. 즉, 11을 부분 문자열로 갖지 않는다.
이와 같은 이친수를 이진수의 크기 순서대로 정렬하여 차례로 번호를 붙인다. 이를테면 첫 번째 이친수는 1, 두 번째 이친수는 10, 네 번째 이친수는 101이 되는 식이다.

자연수 K(1 ≤ K ≤ 1,000,000,000,000,000,000)가 주어졌을 때, K번째 이친수를 찾아내는 프로그램을 작성하시오.

문제접근

1. https://velog.io/@embeddedjune/백준-알고리즘-DP-2193-이친수 에서 약간 발전된 형태다. 지난 문제에서는 길이가 N인 이친수의 모든 개수를 구하는 것이었다면 이번에는 K번째 이친수를 구하는게 문제다.
2. 이전 문제의 solve()함수를 본 문제의 모듈로 사용한다. 여기서는 getCount() 함수라는 이름으로 사용됐으며 구조와 원리는 동일하다.
3. getCount() 함수는 k번째 이친수의 길이를 구하는 getN() 함수의 모듈로 사용된다. getN() 함수는 길이가 1인 이친수부터 개수를 더해가면서 k보다 커질 때의 길이 N을 구하고 길이가 N인 이친수 집합에서 몇 번째 이친수인지 반환하는 함수다.
4. getInnerCount() 함수는 본 문제의 핵심인 함수다.
   • 길이가 N인 이친수 집합에서도 이친수 구조에 따라 구간별로 i번 째부터 j번째 수를 결정할 수 있다.
     • 말이 어려웠다면 예를 들어 설명하겠다. 길이가 7인 이친수 집합에는 100개의 이친수가 포함되어 있다고 가정하자.
     • 그렇다면 1000000이 집합 내에서 가장 작은 이친수이고 이를 점화식의 일부로 표현하면 dp[7][0], 길이가 7인 이친수에서 0으로 끝나는 수이다.
     • 1000001은 이 집합 내에서 1로 끝나는 이친수 중 가장 작은 수이고 dp[7][1]로 표현할 수 있다. 따라서 dp[7][0] = 1, dp[7][1] = 1이다.
     • 그렇다면 dp[6][0], dp[6][1]은 무슨 의미일까?
       길이 7인 이친수에서 6번째 숫자가 0으로 끝나는 이친수와 1로 끝나는 이친수의 경우의 수를 의미한다.
     • dp[6][0] = 2, dp[6][1] = 10이라면, 6번째 숫자가 0으로 끝나는 이친수는 2번째 부터 9번째 수이고 1로 끝나는 이친수는 10번째 부터 시작된다. 이런식으로 나아가면 우리가 구하고자 했던 k번째 이친수가 길이 N인 이친수 집합 내에서 몇 번째 위치에 존재하는지 알 수 있고 숫자까지 알 수 있게 된다.

코드

#include <iostream>
#include <cstring>
using namespace std;
using ll = long long;

static constexpr int MAX = 90;
ll K, len, nthNum;
ll dp[MAX][2], countdp[MAX];

/* 길이가 num인 이친수의 개수를 반환하는 함수 */
ll getCount(int num) {
    if (num < 0) return 0;
    if (num == 0 || num == 1) return num;
    if (countdp[num] > 0) return countdp[num];
    return countdp[num] = getCount(num - 1) + getCount(num - 2);
}
/* K번째 이친수의 길이를 구하고, 해당 길이 내에서 몇 번째 수인지 구하는 함수 */
void getN() {
    ll sum = 0;
    for (int i = 1; i < MAX; ++i) {
        if (sum < K) sum += getCount(i);
        else { 
            K -= (sum - countdp[i - 1]); 
            len = i - 1;    // K번째 이친수의 자릿수 길이
            nthNum = K;     // 해당 길이 내에서 몇 번째 수
            break; 
        }
    }
}
/*  len 길이에 해당하는 이친수 내에서 순서를 결정하는 함수
    총 요소의 개수 = getCount(len)개
    찾고자 하는 이친수 = nthNum번째 이친수
    dp[a][0] = len 길이 이친수 내에서 마지막 숫자가 0이고 부분 길이가 a인 이친수의 개수
    dp[a][1] = len 길이 이친수 내에서 마지막 숫자가 1이고 부분 길이가 1인 이친수의 개수 */
ll getInnnerCount(int length, bool num) {
    if (length == len) return dp[length][num] = 1;   // [기저1]::len 길이까지 만들어짐 = 경우의 수 1
    if (dp[length][num] > 0) return dp[length][num]; // [기저2]::이미 DP에 있으면 갖다씀.
    // [점화식] :: 마지막 숫자 num이 0일 때 다음에 올 수 있는 수는 0과 1, 1일 때는 오로지 0만 옴.
    if (num) dp[length][num] += getInnnerCount(length + 1, 0);
    else dp[length][num] += (getInnnerCount(length + 1, 0) + getInnnerCount(length + 1, 1));
    
    return dp[length][num];
}
/* 답을 출력하는 함수 */
void print(int length, bool num) {
    cout << num;
    if (length == len) { cout << '\n'; return; }
    if (num == 0 && dp[length + 1][0] < nthNum) {   // 이번 숫자가 0이고, 다음 숫자로 1이 올 수 있다.
        nthNum -= dp[length + 1][0];    
        print(length + 1, 1);   
    } else print(length + 1, 0);
}

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    cin >> K;       // 사용자 입력 - K번째 이친수의 'K'값

    getN();
    getInnnerCount(1, 1);
    print(1, 1);
 }

결과