백준 11051 이항 계수2(dynamic programming)

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

11051번: 이항 계수 2

 

#include <iostream>

using namespace std;

const int MAX = 1000 + 1;
const int MOD = 10007;
int N, K;
int c[MAX][MAX];

void binomial()
{
    int m;
    for (int i = 0; i <= N; i++)
    {
        m = (i < K) ? i : K;
        for (int j = 0; j <= m; j++)
        {
            if (j == 0 || i == j)
                c[i][j] = 1;
            else
            {
                c[i][j] = (c[i - 1][j - 1] + c[i - 1][j]) % MOD;
            }
        }
    }
    cout << c[N][K];
}

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

 

이 코드를 외우고 있었어서 되게 쉽게 풀었다. 앞으로 이항계수 문제들은 이 코드 비슷하게 짜면 될 것 같다.

 

m = (i < K) ? i : K;

굳이 하나 설명하자면 이 코드는 5C3과 5C2 값이 같기 때문에 3과 2 중 더 작은 것을 택해서 계산하기 위함이다.