[BOJ 11051] 이항 계수 2 (Java)

BOJ 11051 이항 계수 2

문제풀이

이항계수 nCk는 파스칼의 법칙에 의해서 nCk = n-1Ck-1 + n-1Ck 이다. 이러한 파스칼의 법칙에 따라 삼각형으로 배열한 파스칼의 삼각형을 이용하는 문제다.

• 위의 점화식을 바탕으로 동적계획법을 수행하여 파스칼의 삼각형을 만든다.

구현코드

import java.util.Scanner;

public class Main {
	
	static int[][] pascal;
	static int N, K;
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		K = sc.nextInt();
		
		pascal = new int[1001][1001];
		
		for(int i = 1 ; i <= N ; i++){
	        for(int j = 0 ; j <= N ; j++){
	            if(i == j || j == 0){
	                pascal[i][j] = 1;
	            }
	            else
	            	pascal[i][j] = (pascal[i - 1][j] + pascal[i - 1][j - 1]) % 10007;
	        }
	    }
		
		System.out.println(pascal[N][K] % 10007);
	}
}