#1442 멋진 수

숫자를 2진수로 표현했을 때, 1이 연속으로 3번이상 나오던지 0이 연속으로 3번 이상 나오면 멋진 수라고 정의합니다.

 

주어진 숫자의 범위 안에서 멋진 수가 몇개나 되는지를 알아보는 문제입니다.

숫자의 범위가 21억정도가 되기때문에 이 문제를 풀기 위해서는 범위 안의 숫자를 모두 탐색하는 것은 시간초과가 생길것입니다.

이 문제의 정답자가 적은 이유도 아마 범위안의 숫자를 다 탐색하기 힘들어서일겁니다.

 

이 문제를 풀기 위해서는 첫번째로 멋진 수가 되기 위한 조건이 필요합니다.

 

예를 들어서 10자리의 이진수 숫자가 멋진 수가 얼마나 되는지 알아봐야겠죠.   총 갯수는 792개입니다.

 

전 이것을 계산하기 위해서 멋지지 않은 수가 몇개나 될 것인가를 따졌습니다.

1로 시작하는 10자리의 이진수를 생각한다면,  1001100100 과 같은 수는 멋지지 않은 수입니다.  n자리 멋지지 않은 수의 갯수를  \(T(n)\)이라고 하고 첫 자리수는 1로 시작한다면,

 

\[T(0) = 1\]

\[T(1) = 1\]

이라고 할 수 있습니다.  

 

그러면 \(T(n)\)을 계산하기 위해서는 어떻게 해야할까요?

 

\(T(n)\)은 1로 시작하면서 멋지지 않은 수입니다.  여기에 맨 마지막 자리의 숫자와 다른 수를 넣는 방법은 2가지입니다.  맨 마지막 자리숫자가 1이라면 0을 불이던지 00을 불일 수 있습니다.  0을 붙이면 1자리가 늘어나는 것이고, 00을 붙이면 2자리가 늘어나는 것이기 때문에 우리는 점화식으로 다음과 같이 할 수 있습니다.

 

\[T(n) = T(n-1) + T(n-2)\]

 

자 이러면 우리는 피보나치 수열을 얻게 됩니다. 1 1 2 3 5 8 13 21 34 55 89 .... 라는 수열을 얻게 되겠죠.

10자리 이진수라면 위 식으로부터 1 + 1 + 2 + 3 + 5 + 8 + 13 + 21 + 34 + 55 + 89 = 232 라는 숫자를 얻게 되겠죠.  0부터 1023까지의 숫자 갯수는 1024개이므로 1024 - 232 = 792라는 숫자를 얻게 됩니다.  우리가 원하는 답이죠.

 

그런데 문제는 이것으로만으론 해결이 안 됩니다.

 

바로 숫자 범위가 주어져 있기 때문입니다.  그렇다고, 1500과 같은 숫자가 주어졌을때, 1023까지는 792개이고, 그 후부터 카운팅하는 것은 10억개 이상을 할 수도 있기 때문에 안 됩니다.  10억개에 대해서 처리를 하려면 시간이 많이 걸립니다.

 

그래서 택한 방법은 prefix를 이용한 것이죠.

 

1500은 2진수로 10111011100입니다.  그러면 우리는 prefix를 이용하는데, 1값이 나타나면 0으로 치환한 후에 멋지지 않은 수의 갯수를 구하는 것입니다.  하위 비트부터 시작하면 10111011 + 100이 됩니다.  아래에서 세번째 자리의 1을 0으로 치환하면, 그 후에는 두자리에 대해 멋지지 않은 수를 구하면 됩니다.  일단 101110110 이 멋지지 않은 수여야 합니다.  prefix가 멋진 수라면 뒤에 멋지지 않은 수가 있어도 멋진 수가 되기 때문이죠.  또한 1011101100 도 멋지지 않은 수라면 한자라의 멋지지 않은 수를 구해서 전체 멋지지 않은 수를 구할 수 있습니다.  그런데 중간에 111이 있으므로 멋지지 않은 수는 0이 됩니다.

 

이런 형태를 이용하면 우리는 멋지지 않은 수의 갯수를 구할 수 있습니다.

그리고 그 멋지지 않은 수의 갯수를 원래 숫자로 빼주면 멋진 수의 갯수를 구할 수 있습니다.

 

멋진 수인지 검사하는 것은 다음과 같이 작성하였습니다.

 

//----------------------------------------------------------
//    baekjoon #1442 - Wonderful Number
//        - by Aubrey Choi
//        - created at 2022-07-17
//----------------------------------------------------------
#include <stdio.h>

int f[32];
void pre()
{
    f[0] = 1; f[1] = 1;
    for(int i = 2; i < 32; i++) f[i] = f[i-1] + f[i-2];
}
bool isWonderful(int k)
{
    int zcount = 0, ocount = 0;
    while(k)
    {
        if(k&1) { ocount++; zcount = 0; }
        else { ocount = 0; zcount++; }
        if(ocount == 3 || zcount == 3) return true;
        k >>= 1;
    }
    return false;
}

 

1로 시작하는 n자리수를 계산하는 부분은 pre() 함수로 작성하였습니다.  앞서 이야기했던 점화식을 사용했습니다.

isWonderful(k) 항수는 k가 멋진수이면 true를 반환하는 함수입니다.  1을 만나면 ocount를 증가시키고, zcount를 0으로 초기화합니다.  0을 만나면 반대로 하고요.  그래서 ocount와 zcount가 3이 되면 true를 반환합니다.  이 부분은 prefix가 멋진수인지 아닌지 검사하기 위해 필요합니다.