자연수 N과 정수 K가 주어졌을 때 이항계수 nCk를 10,007로 나눈 나머지를 구하는 프로그램을 작성하시오.
첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 1000, 0 ≤ K ≤ N)
예시 -
5 2
nCk를 10007로 나눈 나머지를 출력한다.
예시 -
10
import java.util.*;
public class Main {
static int[][] memo = new int[1001][1001];
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int r = sc.nextInt();
r = Math.max(r, n-r);
System.out.println(comb(n, r));
}
static int comb(int n , int r) {
for( int i = 1 ; i <= n ; i++) {
memo[i][0] = 1;
memo[i][i] = 1;
}
for( int i = 2 ; i <= n ; i++) {
for( int j = 1 ; j < n ; j++) {
memo[i][j] = (memo[i-1][j-1] + memo[i-1][j]) %10007;
}
}
return memo[n][r];
}
}
처음에는 정말 수학적으로 동적계획법 방식의 factorial함수를 활용하여 코딩했는데, 시간초과가 나서 검색을 통해 이항계수 문제는 파스칼 삼각형을 활용해야한다는 것을 알게되었다.
그 이후로 파스칼의 삼각형을 이용함
이항계수 문제풀이 : 파스칼 삼각형으로!
파스칼 삼각형은 한번 계산한 값이 이후의 계산에서 더해지며 재사용되기 때문에 bottom up 방식으로 메모라이징하는 방식이 가장 적합하다고 생각해서 동적계획법을 활용했다.