[백준] 11051번 이항 계수 2

문제: 11051번: 이항 계수 2

basic-algo-lecture/workbook/0x12.md at master · encrypted-def/basic-algo-lecture

basic-algo-lecture/workbook/0x12.md at master · encrypted-def/basic-algo-lecture

 

#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <algorithm>
#include <cmath>

using namespace std;

int dp[1001][1001];

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

    // dp 테이블 채우고 시작
    for (int i = 1; i <= 1000; i++) {
        // nCn, nC0 은 1임
        dp[i][0] = dp[i][i] = 1;

        for (int j = 1; j < i; j++) {
            dp[i][j] = (dp[i - 1][j - 1] + dp[i - 1][j]) % 10007;
        }
    }

    int n, k;
    cin >> n >> k;
    cout << dp[n][k];

    return 0;
}

 

이항 계수 1 문제와 다르게 n 와 k 의 범위가 커졌다. 즉, for 문을 돌면서 n! 의 값을 구하는 풀이는 불가능하다.

 

이 문제를 풀기 위해서는 dp 를 이용하면 된다. 학창시절에 배웠던 내용인 nCk = n-1Ck-1 + n-1Ck 를 dp 를 통해 구현하면 된다. 사실 구현이라고 말하기엔 쉬워서 좀 그런데.. 아무튼 dp 테이블의 범위를 1001, 1001 로 설정해준 후 for 문을 돌면서 미리 채워놓도록 했다.

 

마지막에 n, k 값을 입력받아서 그대로 dp[n][k] 값을 출력해주면 된다.