BOJ 11051 이항 계수 2

문제

자연수 N과 정수 K가 주어졌을 때 이항 계수 $\binom{N}{K}$를 10007로 나눈 나머지를 구하는 프로그램을 작성하시오.

입력

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

출력

$\binom{N}{K}$를 10007로 나눈 나머지를 출력한다.

문제 분석

1. 정보
   • 자연수 N과 정수 K가 주어졌을 때 이항계수 (N,K)를 10007로 나눈 나머지를 구하는 프로그램을 작성
2. 목표
   • 자연수 N과 정수 K가 주어졌을 때 이항계수 (N,K)를 10007로 나눈 나머지를 구하여 출력
3. 제약 조건
   • $1 \le N \le 10000$
   • $0 \le K \le N$

풀이

1. 아이디어
   • 이항 계수 1 내용에 더불어
   • 모듈러 연산을 이용하여 ((n-1,k-1) % p + (n,k-1) % p)%p 값을 구한 뒤 출력

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class BOJ11051 {

    static int[][] dp;
    static final int p = 10007;

    private static void solution() 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());
        dp = new int[N + 1][K + 1];

        System.out.println(pascalRule(N, K));
    }

    private static int pascalRule(int n, int k) {
        if (dp[n][k] > 0) {
            return dp[n][k];
        }

        if (n == k || k == 0) {
            return dp[n][k] = 1;
        }

        return dp[n][k] = (pascalRule(n - 1, k - 1) % p + pascalRule(n - 1, k) % p) % p;
    }


    public static void main(String[] args) throws IOException {
        BOJ11051.solution();
    }
}

백준 이항 계수 시리즈에 대한 전체적인 내용은 여기를 참고하면 좋다.