[C++][백준 11051] 이항 계수 2

[문제]

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

[문제풀이]

DP를 풀듯이 2차원 배열을 만들어서 풀자.

시간 복잡도는 N^2이기 때문에 1000x1000 배열에서는 1초 안으로 풀 수가 있다.

 

[코드]

#include<iostream>
#include<algorithm>
#include<string>
#define endl "\n"
 
using namespace std;
 
long long result[1001][1001];
 
void combination(int n,int k){
 
    for(int i = 0;i<=n;i++){
        for(int j = 0;j<=k;j++){
            if(i == 0 ){
                result[i][j] = 1;
                continue;
            }
            if(j == 0 or j == i){
                result[i][j] = 1;
                continue;
            }
            result[i][j] = (result[i-1][j] + result[i-1][j-1])%10007;
        }
    }
    return;
}
 
int main(){
    int n,k;
    cin>>n>>k;
    combination(n,k);
    cout<<result[n][k]<<endl;
    return 0;
}