[BaekJoon] 11051번 - 이항 계수 2 [Java]

문제 링크

---

문제 풀이

BaekJoon 11050번 - 이항 계수 1 문제에서 $N$ 과 $K$ 의 범위가 더 커졌고, 이항 계수를 $10,007$ 로 나눈 나머지를 구해야 하는 문제다. 이항 계수는 팩토리얼 연산 때문에 수가 기하급수적으로 커지며 연산량도 많아져서 다이나믹 프로그래밍을 활용해서 효율적으로 구해야 한다.

파스칼의 삼각형을 2차원 dp 배열로 구현하면 되며 행을 $N$, 열을 $K$ 라 했을 때, 아래 점화식으로 이항 계수를 구할 수 있다.

\[dp[n][r] = dp[n-1][r] + dp[n-1][r-1]\]

모듈러 연산은 덧셈에 대해 분배가 가능하므로 이항 계수를 구할 때마다 나머지만 취했다.

---

코드

1. 풀이 [Java]

import java.io.*;
import java.util.*;

public class Main {

    static final int MOD = 10_007;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());

        int[][] dp = new int[1 + N][1 + K];
        for (int n = 0; n <= N; n++) {
            dp[n][0] = 1;

            for (int r = 1; r <= Math.min(n, K); r++) {
                dp[n][r] = (dp[n - 1][r] + dp[n - 1][r - 1]) % MOD;
            }
        }

        System.out.println(dp[N][K]);
    }
}

2. 풀이 [C++]

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

constexpr int MOD = 10007;

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

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

    vector<vector<int>> dp(1 + n, vector<int>(1 + k));
    for (int i = 0; i <= n; i++) {
        dp[i][0] = 1;

        for (int j = 1; j <= min(i, k); j++) {
            dp[i][j] = (dp[i - 1][j] + dp[i - 1][j - 1]) % MOD;
        }
    }

    cout << dp[n][k];
}

---