Pascal Triangle: 이항계수

정의

Pascal Triangle 은 각 원소가 위 두 원소의 합인 삼각형. 행 n, 열 k 의 원소가 이항계수 $\left(\genfrac{}{}{0ex}{}{\{}{n}\right)\}\{k\}$.

1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1

이항계수 $\left(\genfrac{}{}{0ex}{}{\{}{n}\right)\}\{k\}$: n 개 중 k 개를 순서 없이 선택하는 경우의 수.

문제 상황

$\left(\genfrac{}{}{0ex}{}{\{}{n}\right)\}\{k\}$ 를 팩토리얼로 직접 계산하면:

• $n!$ 이 빠르게 오버플로우
• MOD 연산 시 나눗셈 처리 복잡

해결: 점화식 DP 로 MOD 아래서 정확하게 계산.

재귀 점화식:

경계 조건: $\left(\genfrac{}{}{0ex}{}{\{}{n}\right)\}0=(\genfrac{}{}{0ex}{}{\{}{n})\}\{n\}=1$.

시각화

flowchart TD
    C00["C(0,0) = 1"]
    C10["C(1,0) = 1"] --> C20["C(2,0) = 1"]
    C00 --> C10
    C11["C(1,1) = 1"] --> C21["C(2,1) = 2"]
    C10 --> C21
    C00 --> C11
    C11 --> C22["C(2,2) = 1"]
    C21 --> C31["C(3,1) = 3"]
    C20 --> C31
    C21 --> C32["C(3,2) = 3"]
    C22 --> C32
    C20 --> C30["C(3,0) = 1"]
    C22 --> C33["C(3,3) = 1"]

핵심 아이디어

DP 계산

2D 배열 C[i][j]에 파스칼 삼각형 저장. 이전 행에서 두 값을 더하는 O(N^2) 방법.

단일 쿼리라면 1D 배열로 공간 최적화:

• 배열을 오른쪽에서 왼쪽으로 갱신 → in-place 업데이트

MOD 처리

대부분 문제는 답을 $10^9+7$ 로 나눈 나머지 요구.

DP 점화식은 덧셈만 사용하므로 MOD 연산 자연스럽게 적용:

Lucas’ Theorem (대형 n)

n 이 매우 크고 소수 p 로 나눈 나머지를 구할 때:

여기서 $n=\sum n_i{p}^i$, $k=\sum k_i{p}^i$ 는 p 진법 표현.

알고리즘

알고리즘 1: 2D 파스칼 삼각형 (O(N^2) 공간/시간)

// C[i][j] = C(i, j) mod MOD
const int MOD = 1e9 + 7;
vector<vector<long long>> C(n + 1, vector<long long>(n + 1, 0));
for (int i = 0; i <= n; i++) {
    C[i][0] = 1;
    for (int j = 1; j <= i; j++)
        C[i][j] = (C[i-1][j-1] + C[i-1][j]) % MOD;
}
// C[n][k] = C(n, k) mod MOD

알고리즘 2: 1D 공간 최적화 (O(N) 공간)

vector<long long> C(n + 1, 0);
C[0] = 1;
for (int i = 1; i <= n; i++)
    for (int j = i; j >= 1; j--)  // 오른쪽에서 왼쪽으로
        C[j] = (C[j] + C[j-1]) % MOD;
// C[k] = C(n, k) mod MOD

알고리즘 3: 팩토리얼 + 역원 (단일 쿼리 O(N) 전처리)

n 이 크고 다중 쿼리일 때: 팩토리얼과 모듈러 역원을 전처리.

const int MAXN = 2e5 + 5;
const int MOD = 1e9 + 7;
long long fact[MAXN], inv_fact[MAXN];

long long power(long long a, long long b, long long mod) {
    long long res = 1; a %= mod;
    for (; b > 0; b >>= 1) {
        if (b & 1) res = res * a % mod;
        a = a * a % mod;
    }
    return res;
}

void precompute(int n) {
    fact[0] = 1;
    for (int i = 1; i <= n; i++) fact[i] = fact[i-1] * i % MOD;
    inv_fact[n] = power(fact[n], MOD - 2, MOD);
    for (int i = n - 1; i >= 0; i--) inv_fact[i] = inv_fact[i+1] * (i+1) % MOD;
}

long long C(int n, int k) {
    if (k < 0 || k > n) return 0;
    return fact[n] % MOD * inv_fact[k] % MOD * inv_fact[n-k] % MOD;
}

구현

#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9 + 7;
​
int main() {
  int n;
  cin >> n;
  // 파스칼 삼각형 출력
  vector<long long> C(n + 1, 0);
  C[0] = 1;
  for (int i = 0; i < n; i++) {
      vector<long long> nxt(n + 1, 0);
      for (int j = 0; j <= i; j++) {
          nxt[j] = (nxt[j] + C[j]) % MOD;
          nxt[j + 1] = (nxt[j + 1] + C[j]) % MOD;
      }
      C = nxt;
      for (int j = 0; j <= i + 1; j++)
          cout << C[j] << " \n"[j == i + 1];
  }
  // C(n, k) 출력
  int k;
  cin >> k;
  cout << C[k] << "\n";
  return 0;
}

MOD = 10**9 + 7
​
def pascal(n):
  C = [0] * (n + 1)
  C[0] = 1
  rows = []
  rows.append(C[:1])
  for i in range(1, n + 1):
      nxt = [0] * (n + 1)
      for j in range(i + 1):
          if j > 0: nxt[j] = (nxt[j] + C[j-1]) % MOD
          nxt[j] = (nxt[j] + C[j]) % MOD
      C = nxt
      rows.append(C[:i+1])
  return C, rows
​
n = int(input())
C, rows = pascal(n)
for row in rows:
  print(*row)
k = int(input())
print(C[k])

5
2

1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
10

성질

복잡도

함정

흔한 실수

1. C[i][j] 인덱스 오류: j > i 일 때 0 처리 안 함
2. 1D DP 갱신 시 왼쪽에서 오른쪽으로 갱신하면 이미 갱신된 값 사용 (오류)
3. 대형 n 에서 DP 테이블 메모리 초과, 팩토리얼 방법 사용 안 함

BOJ 연습 문제

참고

• 조합론
• Catalan Number
• Inclusion-Exclusion
• 산술 기초