[BOJ 11051] 이항 계수 2

🔗Link

문제
풀이

💡Idea

• 그냥 $nCk = \frac{n!}{k!(n-k)!}$의 공식대로 순차적으로 곱하고 나누면, 곱이 너무 커져서 자료형의 크기를 초과하게 된다.
• $nCk = \binom{n-1}{k-1} + \binom{n-1}{k}$의 공식을 사용하여 dp로 풀면 된다.

🔑Code

#include <bits/stdc++.h>
using namespace std;

int dp[1001][1001];

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

    int N, K;
    cin >> N >> K;
    
    for(int i = 1; i <= N; i++){
        dp[i][0] = 1;
        dp[i][i] = 1;
        for(int j = 1; j < i; j++)
            dp[i][j] = (dp[i-1][j-1] + dp[i-1][j]) % 10'007;
    }

    cout << dp[N][K];

    return 0;
}

🗨️ Side Notes

문제: 어부 4명이 있는데 그중 4명을 전부 고른 것을 이르는 말은?

정답: 어부사시사(어부$_4C_4$​)

이거 하고 싶어서 포스팅 쓴 거 아니다.