[BOJ 11051번] 이항 계수 2(JAVA)

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

11051번: 이항 계수 2

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

public class Main {
	static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
	static BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));
	static StringBuilder sb=new StringBuilder();
	static int[][] combi;
	
	public static void main(String args[]) throws Exception {
		String s[]=br.readLine().split(" ");
		int n=Integer.parseInt(s[0]);
		int k=Integer.parseInt(s[1]);
		combi=new int[n+1][n+1];
		combi[0][0]=combi[1][0]=combi[1][1]=1;
		for(int i=2;i<=n;i++) {
			for(int j=0;j<=i&&j<=k;j++) {
				if(j==0||i==j) combi[i][j]=1;
				else	combi[i][j]=combi[i-1][j-1]+combi[i-1][j];
				combi[i][j]%=10007;
			}
		}
		System.out.println(combi[n][k]);
	}
}

 이 문제 같은 경우는 조합의 공식 중 하나를 사용했습니다.

바로 이 공식인데요, 조합에 대한 이중 배열을 선언한 이후에, nCk 값을 구할 때까지 1C1부터 n과 k의 값을 증가시켜가면서 값을 구했습니다.

이 문제를 풀 때 처음에는 재귀 함수를 이용해서 아래와 같이 문제를 풀었었는데요, 아래 풀이의 경우는 시간 초과 문제가 생겨버렸기 때문에 위의 이중 배열을 사용하는 방법을 추천드립니다.

//시간 초과
import java.util.*;
import java.io.*;

public class Main {
	static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
	static BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));
	static StringBuilder sb=new StringBuilder();
	
	public static void main(String args[]) throws Exception {
		String s[]=br.readLine().split(" ");
		int n=Integer.parseInt(s[0]);
		int k=Integer.parseInt(s[1]);
		System.out.println(combi(n, k));
	}
	
	public static int combi(int n, int k) {
		if(k==0) return 1;
		else if(n==k) return 1;
		else return (combi(n-1, k-1)+combi(n-1, k))%10007;
	}
}