백준 온라인 저지 (BOJ) 11051 이항계수 2

문제

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

입력

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

출력

 C(N,K)를 10,007로 나눈 나머지를 출력한다.

 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

#include<stdio.h> int pascal[1001][1001]; int main() {     int n, k;     scanf("%d%d", &n, &k);     pascal[1][0] = 1;     pascal[1][1] = 1;     for (int i = 2; i <= n; i++) {         for (int j = 0; j <= i; j++) {             if (j == 0)pascal[i][j] = pascal[i - 1][j] % 10007;             else if (j == i)pascal[i][j] = pascal[i - 1][j - 1] % 10007;             else pascal[i][j] = (pascal[i - 1][j - 1] + pascal[i - 1][j]) % 10007;         }     }     printf("%d\n", pascal[n][k]);     return 0; } Colored by Color Scripter

cs

 

파스칼의 삼각형을 이용해서 풀었다.