165. 이항 계수2

백준

1. Python

import sys 
n, k = map(int, sys.stdin.readline().split()) 
dp = [[1 for _ in range(k+1)] for _ in range(n+1)] 
for i in range(1, k+1): 
   for j in range(i+1, n+1): 
       dp[j][i] = (dp[j-1][i-1] + dp[j-1][i]) % 10007 
       
print(dp[n][k])

N, K = map(int, input().split()) 
dp = [[0 for _ in range(N+1)] for _ in range(N+1)] 

for i in range(0, N+1): 
  for j in range(0, N+1): 
    if j == 0: dp[i][j] = 1 
    elif i == j: dp[i][j] = 1 
    elif j == 1: dp[i][j] = i 
    elif N >= K: dp[i][j] = dp[i-1][j-1] + dp[i-1][j] 
    
print(dp[N][K] % 10007)

출처: https://dailylifeofdeveloper.tistory.com/174 [예비개발자의 일상]

2. C++

#include <cstdio>

int cache[1001][1001];

int nCr(int n, int r) {
    if (r == 0) {
        return 1;
    }
    if (n < r) {
        return 0;
    }
    if (n < 0 || 1000 < n || r < 0 || 1000 < r) return 0;

    if (cache[n][r] != -1) {
        return cache[n][r];
    }

    int tmp = (nCr(n - 1, r - 1) + nCr(n - 1, r)) % 10007;
    cache[n][r] = tmp;
    return cache[n][r];
}

int main() {
    for (int i = 0 ; i <= 1000 ; i++) {
        for (int j = 0 ; j <= 1000 ; j++) {
            cache[i][j] = -1;
        }
    }
    int n, k;
    scanf("%d%d", &n, &k);
    printf("%d", nCr(n, k));
}