[백준] 11401번 - 이항 계수 3 [Java]

문제 링크

---

문제 풀이

자연수 $N$ 과 정수 $K$ 에 대한 이항 계수를 1,000,000,007로 나눈 나머지를 구해야 하는 문제다. 단순한 다이나믹 프로그래밍으로는 해결할 수 없는데 페르마의 소정리와 분할 정복을 이용한 거듭 제곱을 적용하면 해결할 수 있다.

이항 계수의 경우 분모를 모듈러 곱셈 역원으로 바꾸면 아래와 같이 된다.(p = 1,000,000,007 이고 p는 소수이며 k!, (n-k)!과 서로소라 모듈러 곱셈 역원이 존재하는 상황)

\[\binom{n}{k} = \frac{n!}{k!(n-k)!} \equiv n!\,(k!)^{-1}\,((n-k)!)^{-1} \pmod{p}\]

이제 팩토리얼과 역팩토리얼 배열을 만들면 저 식의 값을 계산할 수 있는 데, 팩토리얼 배열의 경우 점화식으로 초기화하되 모듈러를 적용해서 오버플로우를 방지했다. 역팩토리얼 배열의 경우 아래 식으로 계산할 수 있다.

\[k! = k\cdot (k-1)!\] \[(k-1)!^{-1} \equiv k \cdot (k!)^{-1} \pmod{p}\]

초항의 경우 페르마의 소정리를 활용하면 아래와 같이 구할 수 있다.

\[k!^{-1} \equiv (k!)^{p-2} \pmod{p}\]

여기서 p-2 = 1,000,000,005 이므로 해당 거듭 제곱 연산을 분할 정복을 이용한 거듭 제곱으로 구하면 된다.

---

코드

1. 풀이 [Java]

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

public class Main {

    private static final int MOD = 1_000_000_007;

    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());

        long[] fact = initFact(N);  // 팩토리얼 배열
        long[] invFact = initInvFact(N, fact[N]);  // 역팩토리얼 배열(모듈러 역원)

        System.out.println(fact[N] * invFact[K] % MOD * invFact[N - K] % MOD);
    }

    private static long[] initFact(int N) {
        long[] fact = new long[1 + N];
        fact[0] = 1;

        for (int i = 1; i <= N; i++) {
            fact[i] = fact[i - 1] * i % MOD;
        }

        return fact;
    }

    private static long[] initInvFact(int N, long a) {
        long[] invFact = new long[1 + N];
        invFact[N] = modPow(a, MOD - 2);  // 역팩토리얼의 초항(페르마의 소정리 활용)

        for (int i = N - 1; i >= 0; i--) {
            invFact[i] = invFact[i + 1] * (i + 1) % MOD;
        }

        return invFact;
    }

    // a^b % mod를 구하는 메서드(분할 정복을 이용한 거듭제곱)
    private static long modPow(long a, int b) {
        if (b == 0) return 1;

        long half = modPow(a, b / 2);
        if (b % 2 == 0) {
            return half * half % MOD;
        } else {
            return half * half % MOD * a % MOD;  // half * half * a가 long형 범위를 넘어갈 수 있어서 미리 mod 수행
        }
    }
}

---

풀이 정보

1. 풀이 [Java]

• 19 min

---