백준(BOJ) 11051번 이항 계수 2

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

문제

자연수 $$N과 정수 $$K가 주어졌을 때 이항 계수 $<span\; style="color:\; rgb(103,\; 0,\; 0);">(</span>\genfrac{}{}{0ex}{}{\mathrm{<span\; style="color:\; rgb(103,\; 0,\; 0);">N</span>}}{\mathrm{<span\; style="color:\; rgb(103,\; 0,\; 0);">K</span>}}<span\; style="color:\; rgb(103,\; 0,\; 0);">)</span>$를 10,007로 나눈 나머지를 구하는 프로그램을 작성하시오.

나의 풀이:

이항계수(N, K) 를 구하는 방법은 (N-1, K-1) + (N-1, K) 이고 재귀적으로 호출해주면 된다. 하지만 N이 1000이기에 시간내에 풀기에는 불가능하다. 

ex ) 이항계수(5, 2)를 예로 이항계수(4,1) 부터 쭉 재귀적으로 내려가서 답을 구한 다고 가정하면 또 (4,2)를 구할 때에도 (3,1), (2,1) 등 구한 값을 다시 구해야 한다. 

따라서 중복이 되는 경우는 메모이제이션을 통하여 중복을 제거 해주어야 한다.

코드 ( C++ )

#include <iostream>

#include <cstring>

using namespace std;

int N, K;

const int MAX = 1000 + 1;

int cache[MAX][MAX];

const int MOD = 10007;

int bino(int n, int k)

{

if (n == k || k == 0) return 1;

int & ret = cache[n][k];

if (ret != -1)

return ret;

return ret = ((bino(n - 1, k) + bino(n - 1, k - 1)))%MOD;   // 10007로 나눈 나머지를 구해주자.

}

int main()

{

memset(cache, -1, sizeof(cache)); // 초기화

cin >> N >> K;

int ans = bino(N, K);

cout << ans << endl;

return 0;

}