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

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

11051번: 이항 계수 2

문제 풀이

이항 계수의 성질 중 다음의 파스칼의 삼각형을 사용하여 풀었다.

처음에 재귀함수를 사용하여 풀이하였으나 그럼 시간 초과가 발생하기에 다음과 같이 dp로 풀이하였다.

#include <iostream>

using namespace std;

int n, k;
int bicos[1005][1005];

int main() {
    ios::sync_with_stdio(0);  
    cin.tie(0);
    cout.tie(0);

    cin >> n >> k;
    bicos[0][0] = bicos[1][0] = bicos[1][1] = 1;
    for(int i = 2; i <= n; i++){
        bicos[i][0] = 1;
        for(int j = 1; j <= k; j++){
            if(i == j) bicos[i][j] = 1;
            else bicos[i][j] = bicos[i-1][j-1] % 10007 + bicos[i-1][j] % 10007;
        }
    }
    cout << bicos[n][k] % 10007;
}