[11051] 이항 계수 2

https://www.acmicpc.net/problem/11051

11051번: 이항 계수 2

 

---

 

🔎 해결 방법

고등학교 확률과 통계에서 배웠던 파스칼의 삼각형 공식만 기억하고 있다면 매우매우 쉬운 문제이다.

 

1 <= r < n 일때

위의 공식은 항상 성립하고 이를 트리로 나타내보면

위와 같은 형태가 된다.

 

따라서 간단한 점화식으로 표현할 수 있고

아래와 같이 표현할 수 있다!

dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j]

 

---

 

💡 내 코드(C++)

// [11051] 이항 계수 2
// https://www.acmicpc.net/problem/11051
// dp
// dp[n][r] = nCr

#include <iostream>
using namespace std;

int main(void)
{
    int n, k;
    int dp[1002][1002];
    cin >> n >> k;
    dp[0][0] = 1; dp[0][1] = 0; 
    
    for(int i = 1 ; i <= n ; i++) {
        dp[i][0] = 1; // nC0 = 1
    }

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

    cout << dp[n][k] << endl;
}