BOJ 11051 - 이항 계수 2

BOJ 11051 - 이항 계수 2

“이항 계수와 동적 계획”

BOJ 11051 - 이항 계수 2

문제 링크


#include <bits/stdc++.h>
using namespace std;

int dp[1001][1001];

// int solve(int n, int k)
// {
//     if (k == 0 || k == n)
//         return 1;
//     return solve(n - 1, k - 1) + solve(n - 1, k);
// }

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

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    int N, K;
    cin >> N >> K;

    int ans = solve(N, K);
    cout << ans;

    return 0;
}

  • 이항 계수의 속성과 알고리즘은 아래 링크를 참조했다.

    -> 이항 계수(Binomial Coefficient)를 구하는 다양한 알고리즘

  • 자연수 및 정수 (n, k)가 주어졌을 때 이항 계수 \(\begin{pmatrix} n \\ k \end{pmatrix}\)를 구하는 법은 \(\begin{pmatrix} n - 1 \\ k \end{pmatrix} + \begin{pmatrix} n - 1 \\ k - 1 \end{pmatrix}\)으로 알려져 있는데, 이것만으로는 문제를 시간 안에 풀어낼 수가 없다. 코드에 주석이 쳐진 재귀 함수 solve()가 이걸 적용한 것인데 올리는 즉시 시간 초과가 뜨게 된다.

int solve(int n, int k)
{
    if (k == 0 || k == n)
        return 1;
    return solve(n - 1, k - 1) + solve(n - 1, k);
}
  • 알아본 결과, 이대로 제출하면 시간 복잡도가 지수함수로 뛰어서 n이 조금만 커져도 문제가 생긴다고 한다. 따라서 시간 안에 문제를 해결하기 위해 따로 배열을 만들고 이항 계수 값을 저장하면서 그 값을 가져다쓰는 동적 계획법을 써먹어야 한다.
int dp[1001][1001];

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

  • 사실 뼈대는 위에 있는 재귀랑 다를 게 없다. dp[i][j] = (dp[i - 1][j - 1] + dp[i - 1][j]) 식이 결국 위의 (n, k) = (n - 1, k - 1)(n - 1, k)와 거의 동일하기 때문이다. 그러나 반복문에 경계 조건이 하나 생겼다. for (int j = 0; j <= min(i, k); j++) 조건문은 k가 n을 넘지 않도록 억제하면서 효과적으로 dp[][] 배열을 채울 수 있도록 해준다.

  • 문제는 (n, k)의 값을 10007로 나눈 나머지를 출력해야 하는데, 애초에 배열에 10007을 나눈 나머지를 기록하면서 진행해야 한다. 그러지 않으면 틀리게 되는데, 아무래도 오버플로우 때문인 것 같다.