Beakjoon 11051 이항 계수2

25 Feb 2021 in Algorithm

문제 링크 : https://www.acmicpc.net/problem/11051

나의 풀이

이항 계수 (n,k) n_C_k = n-1_C_k-1 + n-1_C_k를 다음과 같이 만족한다.

때문에 이항 계수 (n, k)의 값을 DP[n][k]라고 하면 DP[n][k] = DP[n-1][k-1] + DP[n-1][k]이다.
단 k=1 또는 k=n은 항상 1이다.

풀이 코드 : 11051 이항 계수2

#include <iostream>
#include <vector>

using namespace std;

int DP[1001][1001];

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int N,K;
    cin>>N>>K;

    for(int n=1;n<=N;n++){
        for(int k=0;k<=K;k++){
            if(k==0 || k==n){
                DP[n][k] = 1;
            }
            else{
                DP[n][k] = (DP[n-1][k-1] + DP[n-1][k])%10007;
            }
        }
    }
    cout<<DP[N][K];
}

채점결과