백준 11401 이항 계수 3 Java 풀이

문제

n 개중에 k 개를 고르는 이항계수(Binomial Coefficient) 를 구하는 문제이다. 결과값을 1,000,000,007 로 나눈 나머지를 출력한다.

제약사항: 1 <= n <= 4,000,000, 0 <= k <= n

 

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

접근

OutOfMemoryError: Java heap space

일단 숫자가 심상치 않게 크다는 것을 알 수 있다. 이항 계수 2에서 사용했던 이항 계수의 정의를 이용한 풀이를 하려면  4,000,000 * 4,000,000 의 long 타입 heap 메모리 공간( 256,000 GB )을 확보해야한다.

이정도의 heap 메모리 공간을 일반적인 컴퓨터에게 기대할 수 없는 수준이므로 4,000,000 * 16byte = 0.064GB  의 메모리 공간을 요구하는 조합의 정의를 이용한 접근을 활용해야한다.

기존 모듈러 연산의 한계

이항 계수 1 풀이에서 조합의 정의를 이용한 풀이를 보자

import java.util.Scanner;

public class Main {
    private static final int[] CACHE = new int[11];
    public static void main(String[] args) {
        CACHE[0] = 1;
        CACHE[1] = 1;
        CACHE[2] = 2;
        CACHE[3] = 6;
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int K = sc.nextInt();

        System.out.println(factorial(N) / (factorial(N-K) * factorial(K)));
    }

    private static int factorial(int num) {
        if(CACHE[num] != 0) {
            return CACHE[num];
        }
        CACHE[num] = (CACHE[num-1] == 0 ? factorial(num-1) : CACHE[num-1]) * num;
        return CACHE[num];
    }
}

 

 

이항 계수 2 풀이 에서 알아봤던 모듈러 연산 특징은 다음과 같았다.

모듈러 연산의 특징

• 덧셈에 대한 모듈러: (a+b) %  m =((a % m) + (b %  m)) %  m
• 곱셈에 대한 모듈러: (a*b) %  m =((a % m) * (b %  m)) %  m

 

하지만 여기서 어떻게 모듈러 연산을 적용할지 감이 오지 않는다.

각 팩토리얼 연산마다 곱셈에 대한 모듈러 연산을 적용해야하나?

하지만 최종적으로 팩토리얼 연산 결과간 나눗셈이 일어나는데 그때도 이 법칙이 유효한가? 

 

페르마의 소정리

이떄 등장하는게 페르마의 소정리이다.

 

페르마의 소정리 자체는 간단하다.

 어떤 소수 p와 p로 나누어떨어지지 않는 정수 a에 대해 (a^{p-1}) ≡ 1 (mod p) 이 성립한다. 

 

즉 p = 7, a = 3 일때 (3^6) = 729 이고, 729 mod 7 은 1 이 항상 성립한다.

 

이 성질을 어떻게 이용할 수 있을까?

1. 어떠한 실수에 대해 a / b 를 구하기 위해서는 b 의 역원 (b^{-1}) 을 활용할 수 있다는 사실을 알고 있다.

2. 그렇다면 우리는 역원을 이용하여 나눗셈이 있는 식에 대해서 곱셈에 대한 모듈러를 적용할 수 있다.

3. 페르마 소정리에 의해 역원은 (a^{p-1}) ≡ 1 -> (a^{p-2}) ≡ (a^{-1}) 이 성립한다.

4. n!/(n-k!)*k! 식에 대해서 우리는 (n-k!)*k! 에 대한 역원을 구해서 n! * ((n-k!^{p-2})) * ((k!^{p-2})) 로 계산하면 된다.

 

다만 이러한 풀이가 성립하려면 mod 에 적용되는 값이 소수여야 한다. 다행히 주어진 mod 값은 소수이다.

풀이

import java.util.Scanner;

public class Main {
    private static final int MOD = 1_000_000_007;
    private static final int SIZE = 4_000_000;
    private static final long[] factorial = new long[SIZE + 1];

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int K = sc.nextInt();

        // MOD 를 적용한 팩토리얼 값 미리 계산
        computeFactorials();

        // 이항 계수 계산
        long result = (factorial[N] * modInverse(factorial[K]) % MOD) * modInverse(factorial[N - K]) % MOD;
        System.out.println(result);
    }

    private static void computeFactorials() {
        factorial[0] = 1;
        for (int i = 1; i <= SIZE; i++) {
            factorial[i] = (factorial[i - 1] * i) % MOD; // 모듈러 곱셉
        }
    }

    // 모듈러 역원 계산 (페르마의 소정리 이용)
    private static long modInverse(long x) {
        return pow(x, MOD - 2);
    }

    // 거듭제곱 분할 정복으로 x^y % MOD 계산
    private static long pow(long x, int y) {
        long result = 1;
        long base = x;

        while (y > 0) {
            if (y % 2 != 0) {
                result = (result * base) % MOD;
            }
            base = (base * base) % MOD;
            y /= 2;
        }
        return result;
    }
}