[BaekJoon] 11051 이항 계수 2

1.  문제 링크

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

2.  문제

요약

• 자연수 n과 정수 k가 주어졌을 때, nCk를 10,007로 나눈 나머지를 구하는 문제입니다.
• 입력: 첫 번째 줄에 1보다 크거나 같고 1,000보다 작거나 같은 자연수 n과 0보다 크거나 같고 n보다 작거나 같은 정수 k가 주어집니다.
• 출력: 첫 번째 줄에 nCk를 10,007로 나눈 나머지를 출력합니다.

3.  소스코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main {
	final int divisor = 10007;
	public int getCombination(int num, int k) {
		if(k > num / 2) {
			k = num - k;
		}
		if(k == 0 || k == num) {
			return 1;
		} else if(k == 1) {
			return num;
		}
		int[][] dp = new int[num + 1][num + 1];
		for(int i = 0; i < dp.length; i++) {
			for(int j = 0; j <= i; j++) {
				if(i == j || j == 0) {
					dp[i][j] = 1;
				} else {
					dp[i][j] = (dp[i - 1][j - 1] + dp[i - 1][j]) % 10007;
				}
			}
		}
		return dp[num][k];
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		String[] input = br.readLine().split(" ");
		br.close();
		int num = Integer.parseInt(input[0]);
		int k = Integer.parseInt(input[1]);
		Main m = new Main();
		bw.write(m.getCombination(num, k) + "\n");
		bw.flush();
		bw.close();
	}
}

4.  접근

• 해당 문제는 DP를 이용하여 해결할 수 있습니다.
• nCk = nC(n - k)이므로 만약 k가 n / 2보다 크다면 k를 n - k로 변경합니다.
• nCk에서 k가 0이거나 k가 n과 같은 경우는 1, 1인 경우는 n이기 때문에 각 경우에 대해서는 해당 값을 출력합니다.
• 위 경우에 해당하지 않는 경우는 파스칼의 삼각형을 이용하여 풀 수 있습니다.

• 위 그림에서 보면 삼각형에서 어느 한 위치의 값은 자신의 대각선 위 오른쪽 값과 대각선 위 왼쪽 값의 합이 됩니다.
• 예를 들어, 4C2의 값은 (3C1 + 3C2)값이 됩니다.
• 파스칼의 삼각형을 이용하여 파스칼 삼각형의 값들을 나타낼 2차원 배열 dp를 생성하고 삼각형의 각 위치를 돌며 해당 위치에서의 값을 이전의 값들을 이용하여 구합니다.
• nCk에서 k가 0인 경우 혹은 n이 k와 같은 경우는 1이므로 파스칼 삼각형에서 해당 경우에는 1로 설정합니다.
• 만약 그렇지 않은 경우 위에서 설명한 파스칼의 삼각형 성질에 의하여 위의 두 값을 더한 값을 해당 위치의 값으로 설정합니다.
• 문제에서 10007로 나눈 나머지를 출력하라고 하였으므로 위의 두 값을 더한 값을 10007로 나눈 나머지를 해당 위치의 값으로 설정합니다.
• 위 방법을 점화식으로 나타내어 코드로 변환하면 아래와 같은 반복문이 생성됩니다.

for(int i = 0; i < dp.length; i++) {
	for(int j = 0; j <= i; j++) {
		if(i == j || j == 0) {
			dp[i][j] = 1;
		} else {
			dp[i][j] = (dp[i - 1][j - 1] + dp[i - 1][j]) % 10007;
		}
	}
}

• 위 점화식을 바탕으로 (nCk % 10007)을 구합니다.

1. 만약 k가 n / 2보다 크다면 k를 n - k로 변경합니다.
2. 만약 k가 0이거나 k가 n과 같은 경우 1을 출력합니다.
3. 만약 k가 1이라면 n을 출력합니다.
4. 파스칼의 삼각형을 나타내는 2차원 배열 dp를 생성합니다. dp 배열에서 행은 n을 열은 k를 의미합니다.
5. 파스칼 삼각형의 각 위치에 대해 반복문을 돌면서 해당 위치에서의 nCk 값을 구합니다.
   1. n과 k가 같거나 k가 0이라면 해당 위치의 값을 1로 설정합니다.
   2. 만약 그렇지 않다면 현재 위치의 바로 위의 값과 현재 위치에서 대각선 위 왼쪽 값을 더한 후 그 값을 10007로 나눈 나머지 값을 해당 위치의 값으로 설정합니다.(파스칼의 삼각형 성질)
6. 과정 5번의 반복문을 통해 구한 dp 배열에서 dp[n][k]의 값을 출력합니다.