Algorithms/DP Applications

2.16.4 Binomial Coefficients

개념

이항계수 (NR)\binom NR는 서로 다른 NN개 중 RR개를 고르는 경우의 수이며, (x+y)N(x+y)^N을 전개할 때 xN−RyRx^{N-R}y^R의 계수이기도 합니다.

원소를 고르는 경우와 고르지 않는 경우

특정 원소 하나를 정합니다. 그 원소를 고르면 나머지 N−1N-1개에서 R−1R-1개를, 고르지 않으면 나머지에서 RR개를 골라야 합니다.

(NR)=(N−1R−1)+(N−1R).\binom NR=\binom{N-1}{R-1}+\binom{N-1}{R}.

아무것도 고르지 않거나 전부 고르는 경우는 각각 하나이므로 (N0)=(NN)=1\binom N0=\binom NN=1입니다.

A,B,C,DA,B,C,D 중 두 개를 고를 때 DD를 기준으로 나눠 보겠습니다. DD를 고르면 나머지 세 개 중 하나를 골라 AD,BD,CDAD,BD,CD의 33가지입니다. DD를 고르지 않으면 나머지 세 개 중 두 개를 골라 AB,AC,BCAB,AC,BC의 33가지입니다. 모든 선택이 두 경우 중 하나에만 속하므로 합계는 3+3=63+3=6입니다.

파스칼 삼각형

각 행의 양 끝을 11로 두고 바로 위의 두 값을 더합니다. 처음 다섯 행은 11, 1 11\ 1, 1 2 11\ 2\ 1, 1 3 3 11\ 3\ 3\ 1, 1 4 6 4 11\ 4\ 6\ 4\ 1입니다.

팩토리얼 공식은 곱과 나눗셈으로 한 이항계수를 구합니다. 파스칼 삼각형은 작은 이항계수를 저장하고 덧셈만으로 다음 값을 구하므로 여러 N,RN,R에 대해 반복해서 묻는 문제에 유용합니다. 어떤 수로 나눈 나머지가 필요할 때도 각 덧셈 후 나머지를 취할 수 있습니다.

복잡도

이 방법은 나눗셈 없이 덧셈으로 계산하므로 모듈러 연산과 함께 사용할 수 있습니다. 파스칼의 삼각형을 NN번째 행까지 구합니다.

연산시간복잡도공간복잡도
이항 계수 DPO(N2)O(N^2)DP 표 O(N2)O(N^2)

예제

문제

NN개 중 RR개를 고르는 경우의 수를 구하여라.

입력

첫째 줄에 전체 개수 NN과 고를 개수 RR이 공백을 사이에 두고 주어진다. 0≤R≤N≤300\le R\le N\le30이다.

출력

이항계수를 출력한다.

예제 입력

5 2

예제 출력

10

예제 코드

C++20

#include <iostream>

using namespace std;

int dp[31][31];

int main() {
    int n, r, i, j;

    cin >> n >> r;
    for (i = 0; i <= n; ++i) {
        dp[i][0] = 1;
        dp[i][i] = 1;
        for (j = 1; j < i; ++j) {
            dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
        }
    }
    cout << dp[n][r] << '\n';
}