[Java] 백준 11051 이항 계수2

문제

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

 

입력

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

 

출력

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

 

문제 링크 : 이항 계수2

---

설명

처음에 문제를 보고 이항 계수가 뭐지하고 찾아봤던 문제였다. 

나는 정승제의 이항 계수 설명 영상을 보고 이해했다.

이항 계수가 뭔지 모른다면 설명을 듣고 오자!

 

 

이 문제는 주어진 n개의 수 중 k개의 숫자를 뽑는 경우의 수를 구하여 출력해면 된다.

예제1 같은 경우 1 2 3 4 5 총 5개의 숫자 중 2개만 선택하는 경우의 수를 말하는 것이다.

점화식을 구하는 방식은 아래와 같이 구하면 된다.

	0	1	2	3	4	5
1	1	1	0	0	0	0
2	1	2	1	0	0	0
3	1	3	3	1	0	0
4	1	4	6	4	1	0
5	1	5	10	10	5	1

 

1개의 숫자 중 숫자를 하나도 뽑지 않는 경우 => 1가지

1개의 숫자 중 숫자를 1개 뽑는 경우 => 1가지

1개의 숫자 중 숫자를 2개 뽑는 경우 => 숫자가 1개 밖에 없으므로 불가

 

2개의 숫자 중 숫자를 하나도 뽑지 않는 경우 => 1가지

2개의 숫자 중 숫자를 1개 뽑는 경우 => 2가지 (1, 2)

2개의 숫자 중 숫자를 2개 뽑는 경우 => 1가지 (12)

2개의 숫자 중 숫자를 3개 뽑는 경우 => 숫자가 2개 밖에 없으므로 불가

 

3개의 숫자 중 숫자를 하나도 뽑지 않는 경우 => 1가지

3개의 숫자 중 숫자를 1개 뽑는 경우 => 3가지 (1,2,3)

3개의 숫자 중 숫자를 2개 뽑는 경우 => 3가지 (12, 13, 23)

3개의 숫자 중 숫자를 3개 뽑는 경우 => 1가지 (123)

3개의 숫자 중 숫자를 4개 뽑는 경우 => 숫자가 3개 밖에 없으므로 불가

 

이런 식으로 n까지 진행해준 후 최종적으로 k에 해당하는 수를 출력해주면 된다!

 

따라서 점화식은 dp[i][j] = dp[i -1][j] + dp[i -1][j -1] 이 되겠다.

코드

 

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

    public class Main {
        public static void main(String args[]) throws IOException {
            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());
            if (k == 0){
                System.out.println(1);
                return;
            }
            long[][] dp = new long[1001][1001];
            dp[0][0] = dp[1][0] = 1;
            for (int i = 1; i <= n; i ++){
                for (int j = 0; j <= i; j++){
                    if (j == 0) dp[i][j] = 1;
                    else dp[i][j] = (dp[i - 1][j - 1] + dp[i - 1][j]) % 10007;
                }
            }
            System.out.println(dp[n][k] % 10007);
        }
    }