11051 이항 계수2

11051. 이항 계수 / c++ / Silver2 / 11분

문제

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

1. 자연수 N, 정수 K가 주어졌을 때, 이항계수 (N K)를 10’007로 나눈 값을 출력

접근 방식

동적 프로그래밍

1. (N K) 는

   1. K == 0

      K == N 일 때 1이고,

   2. 그 이외에는 (N-1 K-1) + (N-1 K)이다.

문제 풀이

#pragma GCC optimize("Ofast")
#include <iostream>
using namespace std;

int N, K;
int dp[1'001][1'001] = {};

int DP(int n, int k)
{
    if (dp[n][k] == 0)
    {
        if (k == 0 || k == n) dp[n][k] = 1;
        else dp[n][k] = DP(n - 1, k - 1) + DP(n - 1, k);

        dp[n][k] %= 10'007;
    }

    return dp[n][k];
}

int main()
{
    cin >> N >> K;

    cout << DP(N, K) << '\n';

    return 0;
}

다시 생각해 볼 점

1. dp[i] = dp[j] + dp[k] 형식의 문제
2. 10’007로 나눠야한다는 점을 까먹지 말 것