[백준] 11051번 - 이항 계수 2

www.acmicpc.net

https://www.acmicpc.net/problem/11051

문제

💡

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

시간 제한: 1초

메모리 제한: 256MB

입력

💡

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

출력

💡

nCk를 10,007로 나눈 나머지를 출력한다.

예제 입력	예제 출력
5 2	10

풀이

문제를 식으로 표현하면 nCk = (n! / k!(n - k)!) % 10,007 이다. 이 식을 그대로 구현하면 N이 큰 수일 때 팩토리얼과 재귀에서 오버플로가 발생할 수 있다.

처음에 팩토리얼은 반복문으로, 모듈러 연산과 페르마의 소정리를 이용해 코드를 구현했다. 여전히 값이 커 연산이 정확하지 않고, 구현이 복잡해 다른 풀이를 찾아봤다.

의외로 간단하게, 이항 계수의 특징 이용해 DP table을 채워 해결했다. nCk = (n-1)Ck + (n-1)C(k-1), nCk = C(n-1, k) + C(n-1, k-1) 이러면 굳이 팩토리얼이나 재귀를 사용하지 않고 반복문과 몇몇 제어문으로 구현할 수 있다.

코드


#include <iostream>
#include <vector>
using namespace std;
const int M = 10007;

int main() {
	int n, k;
	cin >> n >> k;
	vector<vector<int>> dp(n + 1, vector<int>(k + 1, 0));

	for (int i = 1; i <= n; ++i) {
		for (int j = 0; j <= k && j <= i; ++j) {
			if (i == j || j == 0) {
				dp[i][j] = 1;
			}
			else {
				dp[i][j] = ((dp[i - 1][j] % M) + (dp[i - 1][j - 1] % M)) % M;
			}
		}
	}
	cout << dp[n][k];
	return 0;
}