[DP] BOJ 11051번 이항 계수 2 - 오답노트

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

11051번: 이항 계수 2

- 문제파악

이항계수 n,k 의 값을 10007로 나눈 나머지로 출력하라

 

- 나의 접근

이항 계수 1에서 나머지와 for문을 살짝 바꿔줬는데 해도해도 안되더라..

 

- 정답

점화식을 활용해 메모이제이션을 해야한다.이항 계수의 성질중 하나는 다음과 같다.

 

nCk = (n-1)Ck + (n-1)C(k-1)

 

참고로 위 공식은 파스칼의 삼각형과 같다.

 

위 공식을 점화식으로 메모이제이션을 실시한다.

초항인 k 가 0일때 그리고 k가 n 일때는 값이 1이다.

 

#include "bits/stdc++.h"

using namespace std;

unsigned long long arr[1001][1001];

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

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


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

    cout << arr[n][k];


}