Computer >> 컴퓨터 >  >> 프로그래밍 >> C++

C++로 앞부분과 뒷부분 비트의 합이 같은 짝수 길이 이진 시퀀스 개수 구하기

비트의 개수 n이 입력으로 주어졌을 때, 길이가 2n인 이진 시퀀스 중에서 첫 번째 절반(앞 n비트)의 1의 합과 두 번째 절반(뒤 n비트)의 1의 합이 서로 같은 시퀀스의 개수를 구하는 것이 이 문제의 목표입니다.

문제 접근 방법

이진 시퀀스이므로 각 자리에 올 수 있는 숫자는 0과 1뿐입니다. 따라서 n개의 비트에서 1의 개수에 따라 만들 수 있는 조합의 수는 다음과 같습니다.

  • 1이 0개인 n비트 조합: nC0 = 1
  • 1이 1개인 n비트 조합: nC1
  • 1이 2개인 n비트 조합: nC2
  • ...
  • 1이 n개인 n비트 조합: nCn

길이 2n의 시퀀스에서 앞 절반과 뒤 절반의 1의 개수가 같아야 하므로, 전체 조합의 수는 다음과 같이 계산됩니다.

  • 앞 절반에 1이 0개, 뒤 절반에 1이 0개 → nC0 × nC0
  • 앞 절반에 1이 1개, 뒤 절반에 1이 1개 → nC1 × nC1
  • 앞 절반에 1이 2개, 뒤 절반에 1이 2개 → nC2 × nC2
  • ...
  • 앞 절반에 1이 n개, 뒤 절반에 1이 n개 → nCn × nCn

따라서 총 조합의 수는 다음과 같습니다.

총 개수 = nC0² + nC1² + ... + nCn²

참고로 이 식은 반데르몬드 항등식(Vandermonde's Identity)에 의해 C(2n, n), 즉 2n개 중 n개를 선택하는 조합의 수와 같다는 것이 알려져 있습니다.

입력 및 출력 예시

예시 1

입력: n = 1
출력: 2

설명: 길이 2×1 = 2인 가능한 시퀀스는 00, 01, 10, 11입니다. 이 중 01과 10은 앞 비트와 뒤 비트의 합이 모두 1로 같으므로, 답은 2입니다.

예시 2

입력: n = 2
출력: 6

설명: 길이 2×2 = 4인 가능한 시퀀스는 0000부터 1111까지 총 16개입니다. 이 중 앞 2비트와 뒤 2비트의 합이 같은 시퀀스는 다음과 같습니다.

0000, 0101, 0110, 1001, 1010, 1111 → 총 6개

알고리즘 설명

  1. 정수 bits에 입력값 n을 저장합니다.
  2. findSeq(int n) 함수는 n을 입력받아 앞 절반과 뒤 절반의 합이 같은 길이 2n 시퀀스의 개수를 반환합니다.
  3. 변수 nCi는 nC0 = 1이므로 초기값을 1로 설정합니다.
  4. 결과를 저장할 ans를 1로 초기화합니다(nC0² = 1 포함).
  5. i = 1부터 n까지 반복하면서 아래 점화식으로 nCi를 계산하고, nCi × nCi를 ans에 더합니다.
    nCi / nC(i-1) = (n+1-i) / i
  6. 루프가 종료되면 ans에 저장된 값을 결과로 반환합니다.

C++ 구현 코드

#include<iostream>
using namespace std;

// 앞 절반과 뒤 절반의 합이 같은 짝수 길이 시퀀스의 개수를 반환
int findSeq(int n){
    int nCi = 1; // nC0 = 1
    int ans = 1;
    for (int i = 1; i <= n; i++){
        // nCi / nC(i-1) = (n+1-i) / i
        nCi = (nCi * (n+1-i)) / i;
        ans += nCi * nCi;
    }
    return ans;
}

int main(){
    int bits = 2;
    cout << "앞 절반과 뒤 절반 비트의 합이 같은 이진 시퀀스의 개수: "
         << findSeq(bits);
    return 0;
}

실행 결과

앞 절반과 뒤 절반 비트의 합이 같은 이진 시퀀스의 개수: 6

마무리

이 문제는 조합론의 성질을 활용하면 O(n) 시간 복잡도만으로 효율적으로 해결할 수 있습니다. 모든 이진 시퀀스를 일일이 생성하여 검사하는 브루트포스 방식(O(2ⁿ))과 달리, 이항계수의 제곱합 공식을 이용하면 n이 커져도 빠르게 답을 구할 수 있다는 점이 핵심입니다.