n비트 이진수 중 연속된 1이 없는 숫자 개수 구하기

이 문제에서는 연속된 1이 포함되지 않은 이진수를 찾아야 합니다. 예를 들어 3비트 이진 문자열을 살펴보면, 011, 110, 111처럼 연속된 1을 가진 숫자는 세 개이고, 연속된 1이 없는 숫자는 다섯 개입니다. 따라서 3비트 숫자에 이 알고리즘을 적용하면 답은 5가 됩니다.

a[i]를 비트 수가 i이면서 연속된 1을 포함하지 않는 이진수 집합, b[i]를 비트 수가 i이면서 연속된 1을 포함하는 이진수 집합이라고 하면, 다음과 같은 점화식을 세울 수 있습니다.

a[i] := a[i - 1] + b[i - 1]

b[i] := a[i - 1]

입력

이 알고리즘은 이진수의 비트 수를 입력으로 받습니다. 입력값이 4라고 가정해 보겠습니다.

출력

알고리즘은 연속된 1이 없는 이진 문자열의 개수를 반환합니다.

여기서 결과는 8입니다. 즉, 연속된 1이 없는 이진 문자열이 총 8개 존재합니다.

알고리즘

countBinNums(n)

입력: n은 비트 수
출력: 연속된 1이 없는 숫자의 개수를 계산
Begin
    0으로 끝나는 문자열과 1로 끝나는 문자열 리스트 정의
    endWithZero[0] := 1
    endWithOne[0] := 1
    for i := 1 to n-1, do
        endWithZero[i] := endWithZero[i-1] + endWithOne[i-1]
        endWithOne[i] := endWithZero[i-1]
    done
    return endWithZero[n-1] + endWithOne[n-1]
End

예제 코드

#include <iostream>
using namespace std;
int countBinNums(int n) {
   int endWithZero[n], endWithOne[n];
   endWithZero[0] = endWithOne[0] = 1;
   for (int i = 1; i < n; i++) {
      endWithZero[i] = endWithZero[i-1] + endWithOne[i-1];
      endWithOne[i] = endWithZero[i-1];
   }
   return endWithZero[n-1] + endWithOne[n-1];
}
int main(){
   int n;
   cout << "Enter number of bits: "; cin >> n;
   cout << "Number of binary numbers without consecutive 1's: "<<countBinNums(n) << endl;
   return 0;
}

실행 결과

Enter number of bits: 4
Number of binary numbers without consecutive 1's: 8

위 코드는 동적 계획법(DP)을 활용한 방식으로, 각 자릿수에서 0으로 끝나는 경우와 1로 끝나는 경우를 나누어 누적 계산합니다. 시간 복잡도는 O(n), 공간 복잡도 역시 O(n)으로 매우 효율적입니다. 흥미롭게도 이 결과는 피보나치 수열과 동일한 패턴을 따르는데, 이는 각 단계에서 새로운 비트를 추가할 때 이전 두 상태의 조합으로 경우의 수가 결정되기 때문입니다.