BOJ 11051 - 이항 계수 2

문제 링크

문제#

자연수 $N$과 정수 $K$가 주어졌을 때 이항 계수 $\binom{N}{K}$를 10,007로 나눈 나머지를 구하는 프로그램을 작성하시오.

입력#

첫째 줄에 $N$과 $K$가 주어진다. (1 ≤ $N$ ≤ 1,000, 0 ≤ $K$ ≤ $N$)

출력#

$\binom{N}{K}$를 10,007로 나눈 나머지를 출력한다.

풀이#

이항 계수는 조합 공식을 직접 계산해도 되지만, 현재 구현처럼 파스칼의 삼각형 점화식을 쓰면 훨씬 안정적이다. C(n, k) = C(n-1, k-1) + C(n-1, k)를 그대로 DP로 옮기면 된다.

기저는 양 끝 값이 항상 1이라는 점이다. 그 사이 값들만 이전 줄 두 칸의 합으로 채우면 원하는 조합 수가 차례대로 만들어진다.

결국 직접 곱하고 나누는 대신, 작은 조합을 쌓아 큰 조합을 만드는 방식이다. 모듈러 연산이 있다면 더더욱 DP 쪽이 다루기 편하다.

코드#

#include <iostream>
using namespace std;
 
int C[1001][1001];
 
void solve() {
 
	int n, k;
	cin >> n >> k;
 
	for (int i = 0; i <= n; i++) {
		for (int j = 0; j <= k; j++) {
			
			if (i == j || j == 0) C[i][j] = 1;
			else C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % 10007;
		}
	}
 
	cout << C[n][k] << '\n';
}
 
int main() {
    
    ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
    
	solve();
 
    return 0;
}

복잡도#

• 시간 복잡도: 이항계수 DP 테이블을 채우므로 $O(NK)$이다.
• 공간 복잡도: DP 테이블을 저장하므로 $O(NK)$이다.

마무리#

파스칼 삼각형 점화식 위에 나머지 연산만 얹으면 이항계수도 차분하게 계산된다.