[백준] 11051: 이항계수2

'11051- 이항계수2' 문제로 이동!

👉문제

자연수 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];
	}
	 
}

---

✍Note

처음에는 정말 수학적으로 동적계획법 방식의 factorial함수를 활용하여 코딩했는데, 시간초과가 나서 검색을 통해 이항계수 문제는 파스칼 삼각형을 활용해야한다는 것을 알게되었다.
그 이후로 파스칼의 삼각형을 이용함

이항계수 문제풀이 : 파스칼 삼각형으로!

파스칼 삼각형은 한번 계산한 값이 이후의 계산에서 더해지며 재사용되기 때문에 bottom up 방식으로 메모라이징하는 방식이 가장 적합하다고 생각해서 동적계획법을 활용했다.