연속된 1이 없는 이진 문자열의 개수 구하기

이 문제에서는 연속된 1을 포함하지 않는 이진 문자열의 개수를 구해야 합니다. 예를 들어 3비트 이진 문자열 중에는 011, 110, 111처럼 연속된 1을 가진 세 가지가 있으며, 나머지 다섯 가지(000, 001, 010, 100, 101)는 연속된 1이 없습니다. 따라서 3비트에 이 알고리즘을 적용하면 답은 5가 됩니다.

a[i]를 비트 수가 i이면서 연속된 1을 포함하지 않는 이진 문자열들의 집합, b[i]를 비트 수가 i이면서 연속된 1을 포함하는 이진 문자열들의 집합이라고 정의하면, 다음과 같은 점화식이 성립합니다.

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

이 점화식이 성립하는 이유는 간단합니다. 길이 i인 문자열은 마지막 비트가 0이거나 1입니다. 끝이 0이라면 그 앞에는 어떤 유효한 문자열이든 올 수 있으므로 a[i-1] + b[i-1]개가 되고, 끝이 1이라면 바로 앞 비트는 반드시 0이어야 하므로 a[i-1]개만 가능합니다.

입력 및 출력

입력:
이 알고리즘은 이진수의 비트 수를 입력으로 받습니다. 입력값이 4라고 가정합니다.
출력:
연속된 1이 없는 이진 문자열의 개수를 반환합니다.
여기서 결과는 8입니다. (연속된 1이 없는 이진 문자열은 총 8개)

알고리즘

countBinNums(n)

입력: n은 비트 수입니다.
출력 − 연속된 1이 없는 이진 문자열의 개수를 계산합니다.

Begin
    define lists with strings ending with 0 and ending with 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

동작 원리

endWithZero 배열은 0으로 끝나는 유효한 문자열의 개수를, endWithOne 배열은 1로 끝나는 유효한 문자열의 개수를 저장합니다. 초기값은 모두 1이며(길이 1일 때 "0"과 "1"), 이후 각 단계에서 위의 점화식을 적용해 값을 누적합니다. 최종적으로 두 배열의 마지막 값을 더하면 전체 개수가 됩니다.

C++ 예제 코드

#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 consecitive 1's: "<<countBinNums(n) << endl;
    return 0;
}

실행 결과

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

참고: 피보나치 수열과의 관계

흥미롭게도 이 문제의 답은 피보나치 수열과 밀접한 관련이 있습니다. n비트 이진 문자열 중 연속된 1이 없는 문자열의 개수는 피보나치 수 F(n+2)와 같습니다. 실제로 n=3일 때 F(5)=5, n=4일 때 F(6)=8로 결과가 일치하는 것을 확인할 수 있습니다.