백준 JAVA11 11051번 : 이항 계수 2

이항 계수 2

시간 제한	메모리 제한
1 초	256 MB

문제

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

입력

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

출력

(NK)를 10,007로 나눈 나머지를 출력한다.

예제 입력 1

5 2

예제 출력 1

10

출처

• 데이터를 추가한 사람: BaaaaaaaaaaarkingDog, kimsu00215, loveyourself, skyoliver
• 문제를 만든 사람: baekjoon

알고리즘 분류

• 수학
• 다이나믹 프로그래밍
• 조합론

Idea.

• https://soonhankwon.github.io/til/algorithm11050/
• 푸는 방법은 똑같지만, 10007로 나눈 나머지를 출력하라는 문제이다.
• 모듈러 연산의 특성
  • ( A mod N + B mod N) mod N = ( A + B ) mod N
• 점화식의 결괏값이 나올 때 마다 모듈러 연산을 해준다.

Code.

package combination;

import java.util.Scanner;

public class P11051_binomialCoefficient {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt(); // 총 개수
		int K = sc.nextInt(); // 선택 수

		int[][] DP = new int[N + 1][N + 1];

		for (int i = 0; i <= N; i++) {
			DP[i][i] = 1;
			DP[i][0] = 1;
			DP[i][1] = i;
		}

		for (int i = 2; i <= N; i++) { //  i가 1인경우 선택 수는 모두1 위에서 모두 채워줌 
			for (int j = 1; j < i; j++) {
				DP[i][j] = DP[i - 1][j] + DP[i - 1][j - 1]; 
				DP[i][j] = DP[i][j] % 10007; // MOD
			}
		}
		System.out.println(DP[N][K]);
	}

}