BOJ 백준 2201번 이친수 찾기

 

 

BOJ 백준 2201번 이친수 찾기

 

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

2201번: 이친수 찾기

 

이진수 중에서 다음과 같은 성질을 만족하는 것들을 이친수라고 하자.

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

2. 이친수에서는 1이 두 번 연속으로 니타나지 않는다.

이와 같은 이친수를 이진수의 크기 순서대로 정렬하여 차례로 번호를 붙였을 때, K번째 이친수를 찾아야 한다.

 

우선 각 자리 수마다 이친수가 몇 개 존재하는지를 구해서 K번째 이친수를 찾을 때 자리 수를 활용하고자 한다. 각 자리 수마다의 이친수 개수는 동적 프로그래밍(Dynamic Programming)을 사용해서 구할 수 있다.

 

 

D[N][0]: 길이(자리 수)가 N이고 마지막 숫자가 0인 이친수 개수

D[N][1]: 길이(자리 수)가 N이고 마지막 숫자가 1인 이친수 개수

 

 

자리 수가 N-1인 이친수의 끝에 0을 추가해서 자리 수가 N인 이친수를 만드는 경우, N-1 자리의 이친수의 끝자리는 0이든 1이든 상관 없다. 0은 이친수의 첫 자리에만 오지 않는다면 어떠한 이친수 끝에 붙어도 되어서다. 그러나 N-1 자리의 이친수 끝 자리 숫자가 1인 경우, 1이 두 번 연속으로 나타나지 않아야 되는 이친수의 조건을 만족해야 하므로 뒤에 0만 추가할 수 있다. 이를 정리하면 다음과 같다.

 

 

D[N][0] = D[N-1][0] + D[N-1][1]

D[N][1] = D[N-1][0]

 

 

D[1][0] = 0	D[1][1] = 1	가장 큰 수: 1
D[2][0] = 1	D[2][1] = 0	가장 큰 수: 10
D[3][0] = 1	D[3][1] = 1	가장 큰 수: 101
D[4][0] = 2	D[4][1] = 1	가장 큰 수: 1010

 

 

여기서는 2차원 배열을 사용하여 N 자리의 이친수 개수를 구했지만, 사실 굳이 2차원 배열이 아니라 1차원 배열을 사용해서 이친수 개수를 저장해도 된다. N 자리의 이친수를 만드는 것은 N-1 자리 이친수에 숫자 0 하나를 추거하는 경우에다가 N-2 자리 이친수에 두 자리 "01"을 추가하는 경우를 더한 것과 같기 때문이다. 필기 노트의 '참고' 부분을 보면 자세히 알 수 있다.

 

 

D[N] = D[N-1] + D[N-2]

 

 

단순히 각 자리 수마다의 이친수 개수만 구했다고 해서 K번째의 이친수를 찾을 수는 없다. K라는 서수는 앞에서 누적되어 온 수여서다. 따라서 가장 작은 이친수부터 N 자리 이친수 중 가장 큰 수까지 몇 개의 이친수가 있는지 아는 것이 문제의 목표를 찾는 데 있어서 key가 된다.

 

SUM[N]: 길이(자리 수)가 N인 이친수 중에서 가장 큰 수가 전체 이친수에서 몇 번째인가?

 

가장 작은 이친수부터 N자리 이친수의 가장 큰 수까지 이친수 총 개수는 N-1자리 가장 큰 이친수까지의 개수에 N 자리 이친수 개수를 더한 값이다.

 

 

SUM[N] = SUM[N-1] + D[N][0] + D[N][1]

 

 

D[1][0] = 0	D[1][1] = 1	가장 큰 수: 1	SUM[1] = 1
D[2][0] = 1	D[2][1] = 0	가장 큰 수: 10	SUM[2] = 2
D[3][0] = 1	D[3][1] = 1	가장 큰 수: 101	SUM[3] = 4
D[4][0] = 2	D[4][1] = 1	가장 큰 수: 1010	SUM[4] = 7

 

그러면 K번째 이친수가 어떠한 자리 수를 지니는지 SUM 배열 값을 통해 알 수 있고, 가장 앞 자리 숫자를 제외한 나머지 자리의 이친수 개수를 참고하여 앞 자리부터 가능한 숫자를 차례로 채워나간다.

 

현재 보고 있는 이친수 A가 K번째 이친수이고, A의 자리 수를 N이라고 하자.

 

1) K번째 이친수에서 K가 N-1 자리 이친수 개수보다 작거나 같으면

⇒ 이친수 A는 N-1 이하의 자리 수를 가지므로 맨 앞 숫자로 0이 온다.

 

2) K번째 이친수에서 K가 N-1 자리 이친수 개수보다 크면

⇒ 이친수 A는 N 자리 이친수이므로 맨 앞의 두 숫자로 "10"이 온다.

⇒ 새로 붙인 숫자들을 제외한 뒷부분에 관해 이를 계속 실행하므로 A는 새로 붙인 "10"의 뒷부분이 되고 이에 따라 서수 K 값도 앞에서 숫자를 붙인 그 뒷부분에 해당되는 것으로 대응하여 바뀐다.

 

#include <cstdio>
using namespace std;


const int L_MAX = 100;


long long k;
long long dp[L_MAX + 1][2];
long long sum[L_MAX + 1];


int main(){
    scanf("%lld", &k);
    
    dp[1][1] = 1; sum[1] = 1;
    
    for (int i = 2; i <= L_MAX; i++){
        dp[i][0] = dp[i - 1][0] + dp[i - 1][1];
        dp[i][1] = dp[i - 1][0];
        sum[i] = dp[i][0] + dp[i][1] + sum[i - 1];
    }
    
    if (k == 1){
        printf("1\n");
    }
    else {
        printf("1");
        int n = 0;
        for (int i = 2; i <= L_MAX; i++){
            if (k <= sum[i]) {
                n = i; break;
            }
        }
        k -= (sum[n - 1] + 1);
        n -= 1;
        while (n > 0) {
            if (k > sum[n - 1]){
                printf("1");
                k -= (sum[n - 1] + 1);
            }
            else {
                printf("0");
            }
            n -= 1;
        }
        printf("\n");
    }
    
    return 0;
}