백준 알고리즘 11051번 : 이항 계수 2

링크

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

문제

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

입력

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

출력

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

예제 입력 및 출력

풀이법

1. dp...문제이기 때문에 dp로 풀었다.
2. 이항 계수이기 때문에 nCk = n-1Ck-1 + n-1Ck이 점화식이 성립한다.
3. dp배열을 2차원 배열로 선언하고 n==k이거나 k가 0이면 1의 값을 dp배열에 저장하고, 위의 2번에 있는 점화식을 dp배열로 만들어주기만 하면 되는 문제다.

풀이 코드(C언어)

// 11051번 : 이항 계수 2

#include <stdio.h>
#define mod 10007
#define MAX 1001

int dp[MAX][MAX];

void fibo(int n, int k)
{
    for (int i = 0; i <= n; i++)
    {
        for (int j = 0; j <= k; j++)
        {
            if (i == j || j == 0)
            {
                dp[i][j] = 1;
            }
            else
            {
                dp[i][j] = (dp[i - 1][j - 1] + dp[i - 1][j]) % mod;
            }
        }
    }
}

int main()
{
    int n, k;
    scanf("%d%d", &n, &k);
    fibo(n, k);
    printf("%d\n", dp[n][k]);
    return 0;
}