백준 11051 - 이항 계수 2

icpc.me/11051

11051번: 이항 계수 2

 

이항 계수 $\binom{N}{K}$를 구하는 문제이다.

 

$N \leq 1000$이므로 점화식 $bino(n, k) = bino(n - 1, k) + bino(n - 1, k - 1)$을 단순한 이용한 재귀를 통해서는 구할 수 없다.

 

메모이제이션을 통해 배열에 값을 저장하면 빠르게 계산을 할 수 있다.

 

전체 코드

#include <iostream>
#include <cstring>

using namespace std;

int bino[1001][1001] {};

int solve(int n, int r);

int main()
{
    memset(bino, -1, sizeof bino);
    bino[0][0] = bino[1][0] = bino[1][1] = bino[2][2] = 1;
    bino[2][1] = 2;
    
    int n, r; cin >> n >> r;
    cout << solve(n, r);
}

int solve(int n, int r)
{
    if (n < r || r < 0)
        return 0;
    if (bino[n][r] != -1)
        return bino[n][r];
    
    bino[n][r] = ( solve(n - 1, r) % 10007 + solve(n - 1, r - 1) % 10007 ) % 10007;
    
    return bino[n][r];
}