(C++) - 백준(BOJ) 11051번 : 이항 계수2

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

11051번: 이항 계수 2

dp로 푼 문제였습니다.

 

풀이방법

D[i][j] = nCk;

D[i][j] = D[i-1][j-1] + D[i-1][j]

 

Code

 1. bottom up

#include <iostream>
using namespace std;
long long D[1001][1001],N,K;
int main() {
    cin >> N >> K;
    D[1][0] = D[1][1] = 1;
    for (int i = 2; i <= N; i++)
    {
        for (int j = 0; j <= K; j++)
        {
            D[i][j] += D[i - 1][j - 1] %10007;
            if (i - 1 >= j)
                D[i][j] += D[i - 1][j]%10007;
        }
    }
    cout << D[N][K] % 10007;
}

 

 2. top down

#include <bits/stdc++.h>
#define MOD 10007
using namespace std;
int n,k,a[1001][1001];
//nCk = n-1Ck + n-1Ck-1
int dp(int n, int k){
    if(n == k || k == 0) return 1;
    int &ret = a[n][k];
    if(ret) return ret;
    ret = (dp(n-1,k) % MOD) + (dp(n-1,k-1) % MOD); 
    return ret % MOD;
}

int main(){
    cin >> n >> k;
    cout << dp(n,k);
}