[11051] 이항 계수 2

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

---

import java.util.Scanner;

// 이항계수2
public class Main {
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int K = sc.nextInt();
		int[][] arr = new int[1001][1001];
		
		for(int i=1; i<=1000; i++) {
			for(int j=1; j<=i; j++) {
				if(j==1 || j==i) arr[i][j] = 1;
				else {
					arr[i][j] = (arr[i-1][j]+arr[i-1][j-1])%10007;
				}
			}
		}
		
//		for(int i=1; i<=10; i++) {
//			for(int j=1; j<=i; j++) {
//				System.out.print(arr[i][j] + " ");
//			}
//			System.out.println();
//		}
		
		System.out.println(arr[N+1][K+1]);
		
	}
}

---

이항계수를 구해서 10007로 나눈 나머지를 구하는 문제입니다. 이항계수를 계산하는 정의대로 하면 분자를 계산하고 분모를 계산해서 분자 / 분모 / 10007 을 하면 되지만, 그렇게 하게 되면 주어진 N의 범위 때문에 계산하는 도중에 integer 로 변수를 선언하면 범위를 넘어갑니다. 그래서 저는 파스칼 삼각형을 2차원 배열로 만들어 값을 처음부터 1000까지 구해서 주어진 값을 출력하는 방법으로 문제를 해결했습니다.

[ 문제 풀이 ]

처음 값과 마지막 값은 1로 하고, 나머지 값은 위와 위의 왼쪽값을 더하는 값을 구해서 파스칼 삼각형을 1000 번째 행까지 만들었습니다.

1

1 1

1 2 1

1 3 3 1

1 3 6 3 1

1 4 9 9 4 1

...