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

문제 출처 - Baekjoon Online Judge

문제는 여기

11051번: 이항 계수 2

[문제] 

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

[입력]

첫째 줄에 N\(N\)과 K\(K\)가 주어진다. (1 ≤ N\(N\) ≤ 1,000, 0 ≤ K\(K\) ≤ N\(N\))

[출력]

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

 

 

---

[풀이]

1. 입력을 받아준다.

2. 2중 반복을 돌리면서 i와 j가 같거나 j가 0인 경우는 1을, 아닌 경우는 [i - 1][j - 1]의 값과 [i - 1][j]의 값을 합쳐 더하고 10007을 나눈 나머지를 넣어준다.

3. 결과를 출력한다.

[접근]

1. 파스칼의 삼각형을 생각하고 문제를 풀었다.

2. 점화식 : nCr = n-1Cr-1 + n-1Cr

[코드]

import java.util.*;
import java.io.*;

public class Main {
	static int n, k;

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		// 입력받기
		n = Integer.parseInt(st.nextToken());
		k = Integer.parseInt(st.nextToken());
		
		// 이항계수를 담기 위한 배열
		int[][] coefficient = new int[1001][1001];

		// 파스칼 삼각형
		// 점화식 : nCr = n-1Cr-1 + n-1Cr
		for (int i = 0; i <= n; i++) {
			for (int j = 0; j <= i; j++) {
				if (i == j || j == 0)
					coefficient[i][j] = 1;
				else
					coefficient[i][j] = (coefficient[i - 1][j - 1] + coefficient[i - 1][j]) % 10007;
			}
		}

		System.out.print(coefficient[n][k]);
	}
}