[백준 15791] 세진이의 미팅

문제 출처 : https://www.acmicpc.net/problem/15791

15791번: 세진이의 미팅

이 문제는 결국 남자와 여자가 짝이 되는 모든 조합의 개수를 구하는 문제 입니다. 조합의 개수를 구하기 위해서는 다빈치코딩 알고리즘 조합의 개수에 설명하였습니다. 따라서 이 문제는 결국 아래 식의 값만 구하면 됩니다.

$$ _nC_m = \frac{n * (n-1) * (n-2)... (n-m+1)}{m * (m-1) *(m-2) *... * 2 * 1} $$

숫자가 너무 커지는 것을 방지하기 위해서 1,000,000,007 로 나눈 나머지를 출력해야 합니다. 나머지 연산의 분배 법칙을 사용하면 곱하기 부분은 쉽게 해결할 수 있습니다. 관련 내용은 다빈치코딩 알고리즘 나머지 연산 부분을 확인해 주시기 바랍니다. 문제는 나눗셈을 처리해야 합니다. 나눗셈은 나머지 연산의 분배 법칙이 적용되지 않기 때문에 페르마의 소정리를 이용하여 풀어주어야 합니다. 페르마의 소정리는 이전 포스팅을 확인 바랍니다.

그럼 코드로 작성해 보겠습니다.

입력 받기

N, M = map(int, input().split())
MOD = 1_000_000_007

두 수 N과 M을 입력 받았습니다. 그리고 MOD값을 지정해 주었습니다. 숫자에 _ 가 있어 이상하게 느껴질 수 있습니다. 숫자에 영향을 주지 않는 기호로 숫자를 쓸 때의 쉼표라 생각하면 쉽게 이해될 것입니다.

분모, 분자 구하기

우리가 구해야 하는 것은 n부터 하나씩 줄어들면서 m번째 까지의 곱을 구해야 합니다. 숫자가 너무 커지는 것을 방지하기 위해서 나머지 연산의 분배 법칙을 이용하여 매 번 MOD로 나누어 줍니다. 다음으로 b는 m!로 m부터 1까지의 곱입니다.

a = 1
for n in range(N - M + 1, N + 1):
    a *= n 
    a %= MOD

b = 1
for m in range(1, M + 1):
    b *= m 
    b %= MOD

이것으로 위 식의 분모와 분자를 모두 구하였습니다. 즉 a는 n * (n-1) * (n-2)... (n-m+1) 이고, b는 m * (m-1) *(m-2) *... * 2 * 1 입니다.

페르마의 소정리

페르마의 소정리는 다음과 같습니다.

$$ a^p \equiv a \pmod p $$

양변을 a로 나누면 좌측의 p는 p-1이 되고, 우측의 a는 1이 됩니다.

$$ a^{p-1} \equiv 1 \pmod p $$

여기에 또 a로 나누면 좌측의 p는 p-2가 되고, 우측의 1은 1/a 가 됩니다.

$$ a^{p-2} \equiv \frac{1}{a} \pmod p $$

그럼 아래 식이 성립하게 됩니다.

$$ \frac{a}{b} \equiv a \times b^{p - 2} \pmod p $$

1/b가 b^{p - 2}가 되어 나눗셈을 곱셈으로 바꿔주어 나머지 연산의 분배 법칙을 사용할 수 있게 해주었습니다.

이것을 코드로 나타내면 다음과 같습니다.

result = (a * solve(b, MOD - 2)) % MOD # Fermat’s little theorem
print(result)

a값에 b를 나누어 주는 것이 아니라 b^(mod-2)를 곱해준 것입니다. 나눗셈에 나머지의 분배 법칙을 사용할 수 없어, 곱셈으로 바꾸어 나머지의 분배 법칙을 적용하기 위해서 이렇게 한 것 입니다.

solve 함수

solve 함수는 b를 (mod - 2)번 곱해주는 함수로 거듭제곱을 구하는 용도입니다. 너무 큰 숫자를 계산해야 하기 때문에 분할정복을 이용하여 구해줍니다.

def solve(a, b):
    if b == 1:
        return a % MOD

    result = solve(a, b // 2)
    if b % 2:
        return (result * result * a) % MOD
    else:
        return (result * result) % MOD

다빈치코딩 알고리즘의 곱셈문제에서 해당 내용에 대해 작성해 놓았습니다.

전체 코드

N, M = map(int, input().split())
MOD = 1_000_000_007

def solve(a, b):
    if b == 1:
        return a % MOD

    result = solve(a, b // 2)
    if b % 2:
        return (result * result * a) % MOD
    else:
        return (result * result) % MOD

a = 1
for n in range(N - M + 1, N + 1):
    a *= n 
    a %= MOD

b = 1
for m in range(1, M + 1):
    b *= m 
    b %= MOD 

result = (a * solve(b, MOD - 2)) % MOD # Fermat’s little theorem
print(result)