[백준] 11401번(Java)

📖 이항계수 3

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

---

💡풀이

• 쉽게 생각해서 문제 접근했더니 당연하게도 시간 초과가 나버렸다.
• 이 문제는 페르마의 소정리를 이용해서 풀어야 한다.

페르마의 소정리

• ${\displaystyle p}$가 소수이고, ${\displaystyle a}$가 정수라고 하자. ${\displaystyle p\nmid a}$일 경우(배수 관계가 아닌 경우)
  ${\displaystyle a^{p}\equiv a{\pmod {p}}\qquad (a\neq 0)}$
  ${\displaystyle a^{p-1}\equiv 1{\pmod {p}}\qquad (a\neq 0)}$
  ${\displaystyle a × a^{p-2}\equiv 1{\pmod {p}}\qquad (a\neq 0)}$
• 따라서 $a$ 의 역원은 $a^{p-2}$ 임을 알 수 있다.

위 정리를 바탕으로 문제를 다시 접근해보자

• $\binom{N}{K} = \frac{N!}{K! \cdot (N - K)!} = ({N!}\cdot({{K!}\cdot(N - K)!})^{-1}) \mod P = ({N!}\cdot({{K!}\cdot(N - K)!})^{1,000,000,007 - 2}) \mod P$
• 수식이 정리를 하면 할 수록 복잡해지는 기분이 드는건 왜일까?
• 필자는 ${N!} \mod P$ 와 ${{K!}\cdot(N - K)!})^{1,000,000,007 - 2} \mod P$로 나누어 각각 계산한 뒤, 이를 합쳐서 $mod$ 연산을 진행했다.
• 처음엔 굉장히 악질 문제처럼 보였는데 막상 정리해서 코드 적어보니 생각보다 그렇게까지 악질은 아니라는 생각이 들었다...

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

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static int N, K;
    static int P = 1000000007;

    public static void main(String[] args) throws IOException {
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
        long num = factorial(N, P);
        long denom = factorial(N - K, P) * factorial(K, P);
        System.out.println((num * div(denom, P - 2, P)) % P);
    }
	// 팩토리얼 계산
    private static long factorial(int n, int p){
        if(n == 0) return 1;
        if(n == 1) return 1 % p;
        else return ((n % p) * pib(n - 1, p) % p) % p;
    }
    // 모듈러 연산 공식 이용
    private static long div(long n, long m, long p){
        if(m == 0) return 1 % p;
        if(m == 1) return n % p;
        else{
            long tmp = div(n, m/2, p);
            if(m % 2 == 1){
                return (((tmp * tmp) % p) * (n % p)) % p;
            } else{
                return (tmp * tmp) % p;
            }
        }
    }

}

---

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