[백준 Java]_이항 계수 3 (11401)

문제 정보

• 출처 및 난이도: 백준 골드1
• 링크: https://www.acmicpc.net/problem/11401
• 분류: 페르마의 소정리 및 모듈로 곱셈 역원 (수학), 분할 정복을 이용한 거듭제곱

---

문제 요약

자연수 N 과 정수 K 가 주어졌을 때 이항 계수 C(N, K)를 1,000,000,007로 나눈 나머지를 구하는 프로그램을 작성
N이 최대 4,000,000이라 팩토리얼을 직접 나눌 수 없어서 모듈러 역원이 필요

---

풀이 접근

1. C(N, K) = N! / (K! × (N-K)!) 이므로 분자/분모를 나눠야 함
2. 나머지 연산에서 나눗셈은 직접 불가 → 모듈러 역원을 곱셈으로 대체
3. MOD = 1,000,000,007은 소수이므로 페르마의 소정리 적용 가능
   a^(MOD-1) ≡ 1 (mod MOD) → a의 역원 = a^(MOD-2) mod MOD
   
4. a^(MOD-2)는 분할 정복 거듭제곱으로 O(log N)에 계산

---

핵심 아이디어

• 거듭제곱을 절반씩 쪼개서 계산 횟수를 줄이는 것 → modPow(long a, long b) 참고
  
• 페르마의 소정리: MOD가 소수일 때 a^(-1) ≡ a^(MOD-2) (mod MOD)

  임의의 소수 p에 대해 p와 서로소인 어떤 수의 (p−1)제곱을 p로 나눈 나머지는 무조건 1이라는 정리

• C(N, K) = fact[N] * pow(fact[K] * fact[N-K], MOD-2, MOD) % MOD

---

코드

import java.util.Scanner;

class Main {
    static final long MOD = 1_000_000_007L;

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int N = scanner.nextInt();
        int K = scanner.nextInt();

        scanner.close();

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

    static long solution(int N, int K) {
        if (K < 0 || K > N) return 0;

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

        return fact[N] * modPow(fact[K], MOD - 2) % MOD
                       * modPow(fact[N - K], MOD - 2) % MOD;
    }

    static long modPow(long a, long b) {
        long result = 1;
        a %= MOD;
        while (b > 0) {
            if ((b & 1) == 1) result = (result * a) % MOD;
            a = (a * a) % MOD;
            b >>= 1; // b /= 2
        }
        return result;
    }
}

---

배운 점 / 회고

• 이항 계수 기본 문제도 더 풀어봐야 겠다.
• 아래의 나무위키 및 다른 블로그를 참고했다.
  https://namu.wiki/w/%ED%8E%98%EB%A5%B4%EB%A7%88%EC%9D%98%20%EC%86%8C%EC%A0%95%EB%A6%AC
• 예전에 알고리즘 수업에서 배운 분할 정복과 DP는 아래와 같은 점화식으로 풀이한다.