[백준OJ] 11051번 이항 계수 2

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

11051번: 이항 계수 2

---

 

-풀이-

이항계수의 성질을 알면 dp를 이용하여 쉽게 풀 수 있다. dp[n][r]=k라고할때, nCr = k개 라는 뜻이다.

nCr 이라고 할때

1) n==r 또는 r==0 이면, dp[n][r]=1 이 된다.

2) 1번의 경우가 아닌경우는, dp[n][r]=dp[n-1][r-1]+dp[n-1][r] 이 된다.

 

-시간복잡도-

O(nr) 이 된다.

 

-코드-

#include <algorithm>
#include<iostream>
#define MOD 10007
using namespace std;

int dp[1001][1001]={0};
int n,k;

int main(){
    cin>>n>>k;
    for(int i=1;i<=n;i++){
        for(int j=0;j<=i;j++){
            if(j==0||j==i){
                dp[i][j]=1;
            }
            else{
                dp[i][j]=(dp[i-1][j-1]+dp[i-1][j])%MOD;
            }
        }
    }
    cout<<dp[n][k];
}