[#69][알고리즘] 이항계수 2

백준 > 이항계수 2

문제 링크(https://www.acmicpc.net/problem/11051)

문제

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

입력

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

출력

 $(\genfrac{}{}{0ex}{}{N}{K})$를 10,007로 나눈 나머지를 출력한다.

예제 입력 

5 2

예제 출력 

10

C++풀이

#include <iostream> using namespace std;   int n, k, dp[1001][1001]; int main() {     scanf("%d %d", &n, &k);     dp[0][0] = 1;       for (int i = 1; i <= n; i++) {         dp[i][0] = 1;     }       for (int i = 1; i <= n; i++) {         for (int j = 1; j <= i; j++) {             if (i == j) {                 dp[i][j] = 1;             }             else {                 dp[i][j] = (dp[i - 1][j - 1] + dp[i - 1][j])%10007;             }         }     }     cout << dp[n][k] << endl;       return 0; } Colored by Color Scripter

cs

이항계수 1에서 배열 크기 조절, 10007로 나눈 나머지 부분만 수정