[JAVA] 백준 (실버2) 11051번 이항 계수 2

링크

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

---

문제 설명

정답률 38.141%
자연수 $N$과 정수 $K$가 주어졌을 때 이항 계수 $\binom{N}{K}$를 10,007로 나눈 나머지를 구하는 프로그램을 작성하시오.

---

입력 예제

• 첫째 줄에 $N$과 $K$가 주어진다. $(1 \leq N \leq 1000, 0 \leq K \leq N)$

5 2

---

출력 예제

• $\binom{N}{K}$를 10,007로 나눈 나머지를 출력한다.

10

---

풀이

이항계수는 이항식을 이항정리로 전개했을 때 각 항의 계수를 나타낸다. $(x+y)^2 = x^2 + 2xy + y^2$에서 각 항의 계수인 1, 2, 1이 이항계수이다.

이항계수는 조합을 통해 구할 수 있는데 조합은 점화식을 통해 구할 수 있다. {1, 2, 3, 4, 5} 5개의 데이터가 있을 때 3개를 뽑는 경우의 수는 $_5C_3$이다. 만약 이미 {1, 2, 3, 4}은 선택된 데이터라고 가정할 때 남은 5를 선택한다면 4개중에 2개를 뽑을 수 있고 5가 선택되지 않는다면 4개 중 3개를 뽑을 수 있다. 두 경우의 수를 합한 것이 전체 경우의 수가 되므로 결과는 다음과 같다.

$_5C_3=_4C_2+_4C_3$

이것을 dp배열로 나타내면 다음과 같다.

dp[5][3] = dp[4][2] + dp[4][3];

결론적으로 일반화하면 다음과 같은 점화식으로 나타낼 수 있다.

dp[i][j] = dp[i - 1][j] + dp[i - 1][j - 1];

dp배열을 먼저 초기화한다. $_nC_1 = n$, $_nC_0 = _nC_n = 1$이므로 다음과 같이 초기화 한다.

int[][] dp = new int[N + 1][N + 1];  //메모이제이션 배열
for (int i = 0; i <= N; i++) {
    dp[i][1] = i;  //i개 중 1개를 뽑는 경우의 수
    dp[i][0] = 1;  //1개도 뽑지 않는 경우의 수
    dp[i][i] = 1;  //i개 중 i개를 뽑는 경우의 수
}

그리고 조합 점화식을 이용하는데 10,007으로 나눈 나머지를 구해야 한다. 이때 모듈러 연산의 특성을 이용할 수 있는데 각각 나머지 연산을 수행한 것과 두 수를 더한 후 나머지 연산을 한 결과 값이 동일하다.
$(A mod N + B mod N)modN = (A+B)mod N$

for (int i = 2; i <= N; i++) {
    for (int j = 1; j < i; j++) {
        dp[i][j] = (dp[i - 1][j] + dp[i - 1][j - 1]) % 10007;  //모듈러 연산
    }
}

코드

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

//백준
public class Main {

    public static void main(String[] args) throws IOException {

        System.setIn(new FileInputStream("src/input.txt"));
        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[N + 1][N + 1];  //메모이제이션 배열
        for (int i = 0; i <= N; i++) {
            dp[i][1] = i;  //i개 중 1개를 뽑는 경우의 수
            dp[i][0] = 1;  //1개도 뽑지 않는 경우의 수
            dp[i][i] = 1;  //i개 중 i개를 뽑는 경우의 수
        }

        for (int i = 2; i <= N; i++) {
            for (int j = 1; j < i; j++) {
                dp[i][j] = (dp[i - 1][j] + dp[i - 1][j - 1]) % 10007;  //모듈러 연산
            }
        }

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