C++에서 짝수 인덱스 이항 계수의 합 구하기

숫자 n이 주어졌을 때, 짝수 인덱스에 위치한 이항 계수들의 합을 구하는 문제를 살펴보겠습니다. 즉, 다음과 같은 형태의 값을 계산해야 합니다.

$$\left(\begin{array}{c}n\\ 0\end{array}\right)+\left(\begin{array}{c}n\\ 2\end{array}\right)+\left(\begin{array}{c}n\\ 4\end{array}\right)+\left(\begin{array}{c}n\\ 6\end{array}\right)+...$$

예를 들어 n = 4인 경우는 다음과 같습니다.

$$\left(\begin{array}{c}4\\ 0\end{array}\right)+\left(\begin{array}{c}4\\ 2\end{array}\right)+\left(\begin{array}{c}4\\ 4\end{array}\right)=1+6+1=8$$

접근 방법

가장 기본적인 방법은 파스칼의 삼각형을 이용해 모든 이항 계수를 먼저 구한 뒤, 그중 짝수 인덱스에 해당하는 값들만 골라 더하는 것입니다. 파스칼의 삼각형에서 각 계수는 다음 점화식으로 계산할 수 있습니다.

C(i, j) = C(i-1, j-1) + C(i-1, j)

단, 경계 조건은 C(i, 0) = C(i, i) = 1입니다. 이 점화식을 2차원 배열에 차례대로 채워 나가면 n번째 행에서 필요한 모든 계수를 얻을 수 있습니다.

참고로 수학적으로 흥미로운 성질이 하나 있습니다. 짝수 인덱스 이항 계수의 합은 항상 2^n-1과 같습니다. 실제로 n = 8일 때 2⁷ = 128이 되며, 아래 코드의 실행 결과와 정확히 일치합니다.

예제 코드

#include<iostream>
using namespace std;
int evenIndexedTermSum(int n) {
    int coeff[n + 1][n + 1];
    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= min(i, n); j++) {
            if (j == 0 || j == i)
                coeff[i][j] = 1;
            else
                coeff[i][j] = coeff[i - 1][j - 1] + coeff[i - 1][j];
        }
    }
    int sum = 0;
    for (int i = 0; i <= n; i += 2)
        sum += coeff[n][i];
    return sum;
}
int main() {
    int n = 8;
    cout << "Sum of even placed binomial coefficients: " << evenIndexedTermSum(n);
}

실행 결과

Sum of even placed binomial coefficients: 128

코드 설명

evenIndexedTermSum 함수는 2차원 배열 coeff에 파스칼의 삼각형 방식으로 이항 계수를 채워 넣습니다.

j가 0이거나 i와 같으면(각 행의 양 끝) 계수를 1로 설정합니다.
그 외의 경우에는 바로 윗행의 두 인접 계수를 더한 값으로 계산합니다.
모든 계수를 구한 후, 인덱스를 2씩 증가시키면서 n번째 행의 짝수 위치 계수들을 더해 반환합니다.

이 알고리즘의 시간 복잡도와 공간 복잡도는 모두 O(n²)입니다. 만약 합계 값 자체만 필요하다면 앞서 소개한 2^n-1 공식을 활용해 훨씬 더 효율적으로 답을 구할 수도 있습니다.