백준 11051 이항 계수 2

문제

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

풀이전략

1. 무난하게 nCr = n-1Cr + n-1Cr-1 이라는 고등학교 공식만 알면 풀 수 있다.

코드

#include<bits/stdc++.h>

using namespace std;

int N, K;
int dp[1001][1001];
const int MOD = 10007;
int main(){
    ios_base::sync_with_stdio(false);
    // freopen("../input.txt","rt",stdin);
    
    cin >> N >> K;
    for(int i=1; i<=N; i++){
        dp[i][1] = i;
        dp[i][i] = 1;
        dp[i][0] = 1;
    }

    for(int i = 2; i<=N; i++){
        for(int j= 2; j<=K; j++){
            dp[i][j] = (dp[i-1][j] + dp[i-1][j-1])%MOD;
        }
    }
    cout << dp[N][K] << endl;

    return 0;
}

소감

요즘 코딩테스트를 공부하면서 정말 예전에 수학공부했던 기억이 새록새록 떠올라 재미있다.