[백준] 정수론및조합론 - 11051번 이항계수2 java 자바

문제

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

11051번: 이항 계수 2

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

 

풀이

숫자의 범위가 커졌기 때문에 dp를 이용하여 이항계수를 구한다.

잘 모르겠어서 찾아보면서 했는데 저 answer 함수의 리턴문이 잘 이해되지 않는다.

팩토리얼을 계산할 때 12!과 20!을 넘으면 각각 int형과 long형을 초과하게 되므로 모듈러의 성질을 이용하여 그때 그때 모듈러 계산을 해주는 원리라는데... 다음에 다시 보고 생각해봐야겠다. ㅜㅜ

 

코드

package 정수론및조합론;

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

public class No11051_이항계수2 {

	static int[][] dp;
	static int div = 10007;
	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub
		
		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());
		
		dp=new int[N+1][K+1];
		
		System.out.println(answer(N,K));
	}

	static int answer(int n, int k) {
		if(dp[n][k]>0)
			return dp[n][k];
		
		if(k==0 || n==k)
			return dp[n][k]=1;
		
		return dp[n][k] = (answer(n-1, k-1)+answer(n-1,k))%div;
	}
	
}