C++로 길이 N인 이진 문자열 중 최소 3개의 연속된 1을 포함하는 경우의 수 구하기

정수 N이 주어졌을 때, 길이 N의 모든 이진 문자열 중 최소 3개의 연속된 1을 포함하는 문자열의 개수를 구하는 문제입니다. 예를 들어 n = 4라면 조건을 만족하는 문자열은 0111, 1110, 1111 세 가지이므로 출력값은 3이 됩니다.

동적 계획법(Dynamic Programming)을 활용한 풀이

이 문제는 동적 계획법을 사용하면 효율적으로 해결할 수 있습니다.

DP(i, x)는 길이 i의 문자열 중에서, 위치 i+1부터 i+x까지 x개의 연속된 1을 가지는 문자열의 개수를 의미합니다. 이때 점화식은 다음과 같습니다.

DP(i, x) = DP(i – 1, 0) + DP(i – 1, x + 1)

이 점화식은 i번째 위치에 0 또는 1이 올 수 있다는 사실에 기반합니다.

• i번째 인덱스에 0이 오는 경우: (i – 1)번째 위치에서 x의 값은 0이 됩니다.
• i번째 인덱스에 1이 오는 경우: (i – 1)번째 위치에서 x의 값은 1 + (i번째 위치의 x 값)이 됩니다.

C++ 구현 예제

#include<iostream>
using namespace std;
int n;
int numberCount(int i, int x, int table[][4]) {
    if (i < 0)
        return x == 3;
    if (table[i][x] != -1)
        return table[i][x];
    table[i][x] = numberCount(i - 1, 0, table);
    table[i][x] += numberCount(i - 1, x + 1, table);
    return table[i][x];
}
int main() {
    n = 4;
    int table[n][4];
    for (int i = 0; i < n; i++)
    for (int j = 0; j < 4; j++)
        table[i][j] = -1;
    for (int i = 0; i < n; i++) {
        table[i][3] = (1 << (i + 1));
    }
    cout << "The number of binary strings with at least 3 consecutive 1s: " << numberCount(n - 1, 0, table);
}

실행 결과

The number of binary strings with at least 3 consecutive 1s: 3

위 코드는 메모이제이션(memoization) 기법을 활용하여 이미 계산된 값을 테이블에 저장함으로써 중복 계산을 방지합니다. 재귀 호출이 종료 조건(i < 0)에 도달하면, 그 시점까지 누적된 연속된 1의 개수(x)가 정확히 3인지 확인하여 조건을 만족하는 문자열을 카운트합니다. 이러한 방식으로 전체 탐색 시간을 크게 줄일 수 있습니다.