백준 11051번 이항 계수 2

문제 링크입니다: https://www.acmicpc.net/problem/11051

이산수학 과목에서 이미 조합을 구하는 점화식을 배웠으므로 쉽게 풀 수 있었던 문제였습니다.

/*

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

*/

#include <iostream>

#include <cstring> //memset

using namespace std;

 

const int MAX = 1001;

const int MOD = 10007;

 

int N, K; //주어진 수

int cache[MAX][MAX];

 

int binomialCoef(void) //이항계수

{

        for (int i = 1; i <= N; i++)

        {

               //Combination(i, 1)=i, Combination(i, i)=1, Combination(i, 0)=1

               cache[i][1] = i;

               cache[i][i] = cache[i][0] = 1;

        }

 

        for (int i = 3; i <= N; i++)

               for (int j = 2; j < i; j++)

                       //공식

                       cache[i][j] = (cache[i - 1][j - 1] + cache[i - 1][j]) % MOD;

        return cache[N][K] % MOD;

}

 

int main(void)

{

        cin >> N >> K;

        if (N < 1 || N >= MAX || K<0 || K>N)

               exit(-1);

 

        cout << binomialCoef() << endl;

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~