[BaekJoon] 15791 세진이의 미팅 (Java)

1.  문제 링크

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

2.  문제

3.  소스코드

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

public class Main {
    static final int DIVISOR = 1_000_000_007;
    static long N, M;

    static void input() {
        Reader scanner = new Reader();

        N = scanner.nextInt();
        M = scanner.nextInt();
    }

    static void solution() {
        long nFact = factorial(N) % DIVISOR, mFact = factorial(M) % DIVISOR;
        long base = mFact * factorial(N - M) % DIVISOR;

        long result = nFact * combination(base, DIVISOR - 2) % DIVISOR;
        System.out.println(result);
    }

    static long combination(long base, long exponent) {
        if(exponent == 1)
            return base % DIVISOR;

        long temp = combination(base, exponent / 2);

        long result = temp * temp % DIVISOR;
        if(exponent % 2 == 1)
            result = result * base % DIVISOR;

        return result;
    }

    static long factorial(long number) {
        long result = 1L;

        for(int num = 2; num <= number; num++)
            result = (result * num) % DIVISOR;

        return result;
    }

    public static void main(String[] args) {
        input();
        solution();
    }

    static class Reader {
        BufferedReader br;
        StringTokenizer st;

        public Reader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while(st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }

            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }
    }
}

4.  접근

조합

${_{N}C_{M}} = \begin{pmatrix} N \\ M \end{pmatrix} = \frac{N!} {M!(N-M)!}$

이 문제는 조합을 이용하여 풀 수 있는 문제이다. 그러나 N, M의 범위가 최대 1,000,000이므로 이에 대해 팩토리얼 연산을 진행한다면 long 범위를 넘어가기 때문에 위 수식 그대로 계산하여 구할 수는 없다.

또한 우리는 위 연산을 통해 나온 값을 1,000,000,007로 나눈 나머지를 구해야하는데, 나누기에 대해서는 모듈러 연산의 분배법칙을 적용할 수 없기 때문에 위 수식을 곱셈으로 변경해야 한다.

모듈러 연산

모듈러 연산에는 나눗셈 연산이 없기 때문에 분수 꼴의 수에 대한 모듈러 연산에는 분배법칙을 사용할 수 없다.

그러나 모듈러 연산 기본 성질에 따라 곱셈의 분배 법칙은 성립하기 때문에 나눗셈 연산을 곱셈 연산으로 변경하면 분배법칙을 사용할 수 있다.

$(a \times b) \ mod \ p = ((a \ mod \ p) \times (b \ mod \ p)) \ mod \ p$

분수는 아래와 같이 표현할 수 있다.

$\frac{a} {b} = X \rarr ab^{-1} = X$

• 즉, 우리는 b에 대한 역원을 알 수 있다면 곱셈 꼴로 분수를 변환할 수 있으니 모듈러 연산의 곱셈에 대한 분배법칙을 사용할 수 있다.
• b의 역원을 구하기 위해서 페르마의 소정리를 이용한다.

페르마의 소정리

a는 정수, p는 소수이며, a와 p가 서로소일 때,
$a^{p} \equiv a \ (mod \ p) \\ \rarr a^{p} \ mod \ p \equiv a \ mod \ p$

위 식을 정리하면 아래와 같이 표현할 수 있다.

$a^{p - 1} \equiv 1 \ (mod \ p) = a \times a^{p - 2} \equiv 1 \ (mod \ p)$

• 위 식을 통해 알 수 있는 것은 a의 역원이 $a^{p-2} \ (mod \ p)$라는 사실이다.

우리가 구하고자 하던 식은 아래와 같다.

$\frac{N!} {M!(N - M)!} \ mod \ p \ = (N! \times (M!(N - M)!)^{-1}) \ mod \ p \\ = ((N! \ mod \ p) \times (M!(N - M)!)^{-1} \ mod \ p) \ mod \ p$

페르마의 소정리를 통해 역원을 구하는 방법을 알게 되었으니, 역원 식의 a와 p를 우리가 구하고자 하는 식에 맞게 변형해보면 아래와 같다.

• $a = (M!(N - M)!), p = 1,000,000,007 \\ \rarr (M!(N - M)!)^{-1} = (M!(N - M)!)^{1,000,000,007 - 2}$
• 분수 꼴이어서 모듈러 연산의 분배법칙을 적용하지 못한 문제를 위 식을 통해 해결할 수 있게 된다.

그럼 이제 우리가 최종적으로 구하고자 하는 식은 아래와 같다.

$\frac{N!} {M!(N-M)!} \ mod \ p = (N! \times (M!(N - M)!)^{-1}) \ mod \ p = \\ ((N! \ mod \ p) \times (M!(N - M)!)^{-1} \ mod \ p) \ mod \ p = \\ ((N! \ mod \ p) \times (M!(N - M)!)^{1,000,000,007 - 2} \ mod \ p) \ mod \ p$

위 수식을 이용하여 이 문제의 답을 구한다.

• 이때 1,000,000,005번 제곱을 할 수 없으니, 분할 정복을 이용하여 제곱을 진행한다.

  static long combination(long base, long exponent) {
      if(exponent == 1)
          return base % DIVISOR;
  
      long temp = combination(base, exponent / 2);
  
      long result = temp * temp % DIVISOR;
      if(exponent % 2 == 1)
          result = result * base % DIVISOR;
  
      return result;
  }