C++에서 연속된 0의 쌍 개수 구하는 방법

문제 소개

1에서 시작하는 수열 생성기가 있다고 가정해 보겠습니다. 이 생성기는 각 단계가 진행될 때마다 0은 '10'으로, 1은 '01'로 변환합니다. 따라서 단계가 거듭될수록 수열은 다음과 같이 변화합니다.

1단계 – 01
2단계 – 1001
3단계 – 01101001 …

목표는 주어진 단계 수에서 연속된 두 개의 0('00')이 등장하는 쌍의 개수를 구하는 것입니다. 예를 들어 단계가 1일 때 0의 쌍은 0개, 단계가 2 또는 3일 때는 각각 1개입니다.

4단계 – 1001011001101001
5단계 – 01101001100101101001011001101001

패턴 분석과 공식 유도

수열을 자세히 관찰하면 흥미로운 규칙을 발견할 수 있습니다. 수열의 길이는 단계마다 2배씩 늘어나 2의 거듭제곱 형태로 성장하며, 내용은 길이 12를 주기로 반복됩니다. 그리고 길이 12짜리 각 패턴 안에는 연속된 0의 쌍이 정확히 2개씩 포함되어 있습니다.

이를 바탕으로 단계 S에서의 쌍 개수는 다음 공식으로 계산할 수 있습니다.

tmp = 2^S ÷ 12 (정수 나눗셈)
연속된 0의 쌍 개수 = 1(초기값) + 2 × tmp

예시 1

입력 – steps = 5

출력 – 연속된 0의 쌍 개수: 5

설명 – 5단계 수열은 다음과 같으며, 실제로 '00'이 5번 등장합니다.

Step 5: 01101001100101101001011001101001

공식으로도 확인할 수 있습니다. tmp = 2⁵ ÷ 12 = 32 ÷ 12 = 2이므로, 쌍의 개수 = 1 + 2 × 2 = 5입니다.

예시 2

입력 – steps = 10

출력 – 연속된 0의 쌍 개수: 171

설명 – 공식에 대입하면 tmp = 2¹⁰ ÷ 12 = 1024 ÷ 12 = 85이므로, 쌍의 개수 = 1 + 2 × 85 = 171입니다.

접근 방법

위 프로그램에서 사용한 접근 방식은 다음과 같습니다. 먼저 단계 수를 입력받고, steps가 1이면 연속된 0의 쌍은 0개, steps가 2 또는 3이면 1개임을 확인합니다. 그 외의 경우에는 공식 tmp = 2^steps ÷ 12와 pairs = 1 + 2 × tmp를 이용해 계산합니다.

알고리즘 단계

단계 수를 담을 변수 decimal을 선언하고 값을 입력받습니다.
함수 Zero_pairs(int decimal)는 decimal을 받아 해당 단계에서 연속된 0의 쌍 개수를 반환합니다.
초기 카운트(count)를 0으로 설정합니다.
decimal ≤ 1이면 0을 반환합니다.
decimal이 2 또는 3이면 1을 반환합니다.
그 외의 경우 temp = pow(2, decimal) / 12를 계산하고, count = 2 × temp + 1로 구합니다.
count를 결과로 반환합니다.

C++ 구현 예제

#include<bits/stdc++.h>
using namespace std;
int Zero_pairs(int decimal){
    int count = 0;
    if(decimal <=1){
        count = 0;
    }
    else if(decimal == 2 || decimal == 3){
        count = 1;
    }
    else{
        int temp = (pow(2, decimal) / 12);
        count = 2 * temp + 1;
    }
    return count;
}
int main(){
    int decimal = 7;
    cout<<"Count of Pairs Of Consecutive Zeros are: "<<Zero_pairs(decimal);
    return 0;
}

실행 결과

위 코드를 실행하면 다음과 같은 출력이 생성됩니다.

Count of Pairs Of Consecutive Zeros are: 21

decimal이 7일 때 temp = 2⁷ ÷ 12 = 128 ÷ 12 = 10이므로, 쌍의 개수 = 2 × 10 + 1 = 21이 됩니다.

참고 사항

이 알고리즘은 단순 공식 계산만 수행하므로 시간 복잡도는 사실상 O(1)로 매우 효율적입니다. 다만 pow 함수는 부동소수점을 반환하기 때문에 단계 수가 커지면 정밀도 오류가 발생할 수 있으므로, 실무에서는 비트 시프트 연산자(1 << decimal)를 사용해 2의 거듭제곱을 정수로 직접 계산하는 것이 더 안전합니다.