[BOJ-11051][C++] 이항 계수 2

문제

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

 

입력

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

 

출력

${N \choose K}$ 를 10,007로 나눈 나머지를 출력한다.

 

예제 입력 1

5 2

 

예제 출력 1 

10

 

알고리즘 분류

• 수학
• 다이나믹 프로그래밍
• 조합론

 

문제 출처

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

11051번: 이항 계수 2

 

---

 

문제 해결 방법

• 이항 계수를 구하는 알고리즘을 메모이제이션(Memoization)으로 구현하여 문제를 해결하였다.
• 이 때 주의할 점은 메모이제이션을 할 때마다 10,007로 나눈 나머지를 dp 배열에 넣어줘야 한다는 것이다. (그렇지 않을 경우 자료형의 크기를 초과하여 틀리게 된다.)

#define DIV 10007

int nCk(int n, int k) {
    if (dp[n][k] > 0) return dp[n][k];
    else if (k == 0 || k == n) return dp[n][k] = 1;
    else if ((0 < k) && (k < n)) return dp[n][k] = (nCk(n - 1, k - 1) + nCk(n - 1, k)) % DIV;
    else return 0;
}

 

코드

#include <iostream>
using namespace std;

#define DIV 10007

int dp[1001][1001], N, K;

int nCk(int n, int k) {
    if (dp[n][k] > 0) return dp[n][k];
    else if (k == 0 || k == n) return dp[n][k] = 1;
    else if ((0 < k) && (k < n)) return dp[n][k] = (nCk(n - 1, k - 1) + nCk(n - 1, k)) % DIV;
    else return 0;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> N >> K;
    
    cout << nCk(N, K) << '\n';

    return 0;
}

 

채점 결과

 

참고

• [단계별로 풀어보기] > [정수론 및 조합론]
• 실버II