[BOJ/Java] 11401. 이항 계수 3

[BOJ/Java] 11401. 이항 계수 3

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

---

문제 해석

이항 계수 3 문제는 주어진 자연수 \(N\)과 \(K\)에 대해 이항 계수 \(\binom{N}{K}\)를 \(1,000,000,007\)로 나눈 나머지를 구하는 문제이다. 이항 계수는 다음과 같이 정의된다: \[ \binom{N}{K} = \frac{N!}{K!(N-K)!} \] 이 문제는 \(N\)과 \(K\)가 매우 크기 때문에(\(1 \leq N \leq 4,000,000\), \(0 \leq K \leq N\)), 직접 계산하는 대신 **페르마의 소정리**와 **모듈로 연산**을 활용하여 효율적으로 해결해야 한다.

풀이 과정

1. 페르마의 소정리 적용: 페르마의 소정리에 따르면, 소수 \(p\)에 대해 \(a^{p-1} \equiv 1 \ (\text{mod} \ p)\)이다. 이를 활용하여 분모의 역원을 계산한다: \[ \frac{1}{K!(N-K)!} \equiv (K!(N-K)!)^{p-2} \ (\text{mod} \ p) \]
2. 팩토리얼 계산: \(N!\), \(K!\), \((N-K)!\)를 미리 계산한다. 이때, 모듈로 \(1,000,000,007\)을 적용하여 오버플로를 방지한다.
3. 역원 계산: \(K!\)와 \((N-K)!\)의 역원을 페르마의 소정리를 통해 계산한다.
4. 이항 계수 계산: \(N! \times (K!)^{-1} \times ((N-K)!)^{-1} \ (\text{mod} \ p)\)를 계산하여 최종 결과를 구한다.

코드

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

public class Main {
    static final long 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[] factorial = new long[N + 1];
        factorial[0] = 1;
        for (int i = 1; i <= N; i++) {
            factorial[i] = (factorial[i - 1] * i) % MOD;
        }

        // 역원 계산 (페르마의 소정리)
        long denominator = (factorial[K] * factorial[N - K]) % MOD;
        long inverseDenominator = pow(denominator, MOD - 2);

        // 이항 계수 계산
        long answer = (factorial[N] * inverseDenominator) % MOD;
        System.out.println(answer);
    }

    // 분할 정복을 이용한 거듭제곱 계산
    static long pow(long base, long exponent) {
        if (exponent == 1) return base % MOD;
        long half = pow(base, exponent / 2);
        long result = (half * half) % MOD;
        if (exponent % 2 == 1) result = (result * base) % MOD;
        return result;
    }
}

시간 복잡도 분석

시간 복잡도는 O(N + log MOD)이다. 팩토리얼을 계산하는 데 O(N), 역원을 계산하는 데 O(log MOD)의 시간이 소요되기 때문이다. 이는 문제의 제약 조건 내에서 효율적으로 동작한다.

느낀점

이 문제는 페르마의 소정리와 모듈로 연산을 활용하여 이항 계수를 효율적으로 계산하는 방법을 배울 수 있는 좋은 문제이다. 특히, 큰 수의 팩토리얼과 역원을 계산하는 과정에서 수학적 지식의 중요성을 느낄 수 있었다. 이러한 문제는 조합론이나 암호학 등 다양한 분야에서 활용될 수 있을 것 같다.