[자바] 백준 11051번: 이항 계수2

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

11051번: 이항 계수 2

 

이항 계수 1과 같은 문제지만, 조건이 1<=N<=1,000으로 수의 범위가 늘어났다.

 

팩토리얼을 이용해서 이항계수를 계산하게 되면,

팩토리얼(n)에서 n이 20정도만 넘어도 숫자가 엄청나게 커져서 

스택오버플로우 등이 발생할 수 있고 계산하는데에도 시간이 오래 걸린다.

 

이번에는

C(n+1,k+1) = C(n,k) + C(n, k+1)

이라는 성질을 이용하여

파스칼의 삼각형을 만들어서 문제를 풀었다.

 

이차원 배열을 만들어서,

n==k 또는 k==0인 경우에는 1을 넣고,

그렇지 않은 경우에는 C(n-1,k-1) + C(n,k+1) 값을 넣었다.

그런데 숫자가 엄청나게 커지게 되므로

문제에서 요구하는 %10007을 배열에 넣을 때 미리 계산해서 넣으면 된다.

 

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

public class P11051 {

	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[][] arr = new int[n + 1][n + 1];

		for (int i = 0; i < arr.length; i++) {
			for (int j = 0; j <= i; j++) {
				if (i == j || j == 0)
					arr[i][j] = 1;
				else
					arr[i][j] = (arr[i - 1][j - 1] + arr[i - 1][j])%10007;
			}
		}
		System.out.println(arr[n][k]);
	}

}