백준 11051번: 이항 계수 2

백준 11051번: 이항 계수 2

 

수학문제로 문제는 쉬워보이는데 생각보다 정답률이 낮았다. 역시나 예상대로 그냥 아무생각없이 팩토리얼 계산으로 푸는 문제는 아니었다.

 

이항 계수(n, k) 출처 : 위키백과

0 <= k <= n 이라는 식을 만족할 때 이항계수는 nCk라는 값을 가지고 이러한 식의 값을 나열했을 때 나오는 표가 삼각형을 이루는데 이러한 삼각형을 파스칼 삼각형이라고 부른다. 

이항 계수 항등식

<파스칼 법칙> 이러한 점화식을 가질 수 있다.

파스칼 삼각형은 다음과 같은 모양으로 나온다.

파스칼 삼각형

 

점화식 풀이를 코드화 하자면

 

이항계수[N_number][K_number] = 이항계수[N_number - 1][K_number-1] + 이항계수[N_number-1][K_number]

 

이러한 알고리즘 코드를 도출할 수 있을 것이다.

삼각형의 테두리에만 유의해서 코드화하고 결과값을 문제에 나와있는 10007로 나누는 것만 잊지 않는다면 쉽게 풀 수 있다.

 

#include<iostream>
using namespace std;

int dp[1001][1001];

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

    int n, k;
    cin >> n >> k;

    for(int i = 1; i <= n; i++){
        for(int j = 0; j <= n; j++){
            if(i == j || j == 0){
                dp[i][j] = 1;
            }
            else
            	dp[i][j] = (dp[i-1][j] + dp[i-1][j-1]) % 10007;
        }
    }
    cout << dp[n][k];
    return 0;
}