문제
자연수 N과 정수 K가 주어졌을 때 이항 계수 N Combination K를 10,007로 나눈 나머지를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ K ≤ N)
출력
N Combination K를 10,007로 나눈 나머지를 출력한다.
예제 입력 1
5 2 |
예제 출력 1
10 |
더보기
Solution
#include<stdio.h>
#include<stdlib.h>
int main(void)
{
int N, K, **C=NULL;
scanf("%d %d", &N, &K);
C=(int **)malloc((N+1)*sizeof(int *));
K=K*2>=N?N-K:K;
for(int c=0;c<=N;c++)
C[c]=(int *)calloc(K+1,sizeof(int));
C[0][0]=1;
for(int i=1;i<=N;i++)
{
C[i][0]=1;
for(int j=1;j<=K;j++)
C[i][j]=(C[i-1][j-1]+C[i-1][j])%10007;
}
printf("%d\n", C[N][K]);
for(int c=0;c<=N;c++)
free(C[c]);
free(C);
return 0;
}
728x90
'백준 알고리즘' 카테고리의 다른 글
<백준 알고리즘> 2193번: 이친수 (0) | 2021.02.13 |
---|---|
<백준 알고리즘> 1747번: 소수&팰린드롬 (0) | 2021.02.09 |
<백준 알고리즘> 2579번: 계단 오르기 (0) | 2021.02.08 |
<백준 알고리즘> 2947번: 나무 조각 (0) | 2021.02.05 |
<백준 알고리즘> 1568번: 새 (0) | 2021.02.05 |