[백준/Python]11401: 이항 계수 3

문제

https://www.acmicpc.net/problem/11401
백준 단계별 풀이 - 분할 정복

---

풀이

이항계수가 주어졌을 때, 이항계수 (N K)를 1,000,000,007로 나눈 나머지를 구해야한다.

 

이항계수를 구하는 공식은 nCk = n!/(k!(n-k)!) 다.
정리하면 아래와 같다.

(n * (n-1) * (n-2) * (n-k+1) 여기부터 (n-k)! * (n-k) * (n-k-1) * ... * 2 * 1)
/ (k * (k-1) * (k-2) * ... * 2 * 1)((n-k) * (n-k-1) * ... * 2 * 1)
=> (n * (n-1) * ... * (n-k+1)) / (k * (k-1) * ... * 2 * 1)

 

그리고 이 값들을 1,000,000,007로 나누어줘야한다.
이걸 분할정복으로 풀려면 어떻게 풀어야 하나...😶‍🌫
일단 팩토리얼을 구하는 함수를 만들어서 단순계산 형식으로 짜봤다.

N, K = map(int, input().split())
namerge = 1000000007

def factorial(start, end):
    ret = 1
    for i in range(start, end+1):
        ret *= i

    return ret % namerge

print(factorial(N-K+1, N) // factorial(2, K) % namerge)

결과는 당연히 시간 초과다.

끙끙대다가 결국엔 구글링...
주어진 시간내에 통과하려면 모듈러 연산, 페르마의 소정리 개념을 사용해야했다.

 

모듈러 연산

나눗셈의 나머지를 다루는 연산이다.
a를 m으로 나눈 나머지와 b를 m으로 나눈 나머지가 같다고 했을때,
$ a \equiv b  (mod  m) $ 으로 나타낼 수 있다.

 

모듈러 연산은 덧셈, 뺄셈, 곱셈에 대해 분배법칙을 사용할 수 있다.
형태는 다음과 같다.
덧셈: $ (A + B)  mod  C = (A  mod  C + B  mod  C)  mod  C $
뺄셈: $ (A - B)  mod  C = (A  mod  C - B  mod  C)  mod  C $
곱셈: $ (A * B)  mod  C = ((A  mod  C) * (B  mod  C))  mod  C $

하지만 이항계수를 구하는 공식은 나눗셈이기 때문에, 모듈러 연산을 사용하려면 곱셈 형태로 변경해야한다.
이항계수를 p로 나눈 식을 곱셈 형태로 변경하면 $ N! * (K! * (N-K)!)^{-1}  mod  p $ 가 된다.

 

왜 굳이 모듈러 연산을 사용해야 하는가?
=> $ N! * (K! * (N-K)!)^{-1} $가 매우 커질수도 있기 때문이다.

 

이제 위의 식에 모듈러 연산을 적용하면,
$ (N!  mod  p * ((N-K)!K!)^{-1}  mod  p)  mod  p $가 만들어진다.

하지만 -1을 제곱하면 정수가 아닌 값이 만들어지므로 정확도가 떨어진다.
-1을 양의 정수값으로 대체하기 위해 페르마의 소정리가 필요하다.

 

페르마의 소정리

p가 소수이고 a가 p의 배수가 아닌 정수일 때, $ a^{p-1} \equiv 1  mod  p $ 가 성립한다.
(등호 세개는 합동이라는 의미다. 합동은 '어떤 정수로 나눈 나머지가 서로 같은 두 정수 사이의 관계'를 뜻한다.)

위의 식 양변에 $ a^{-1} $ 을 곱해주면, $ a^{p-2} ≡ a^{-1}  (mod  p) $ 가 된다!

즉, 모듈러 연산을 통해 구한 값 $ (N!  mod  p * ((N-K)!K!)^{-1}  mod  p)  mod  p $을
$ (N!  mod  p * ((N-K)!K!)^{p-2}  mod  p)  mod  p $로 대체할 수 있게 된다.

 

정답 코드

N, K = map(int, input().split())
p = 1000000007

def factorial(n):
    ret = 1
    for i in range(2, n+1):
        ret = (ret * i) % p
    return ret

def square(n, k):
    if k == 0:
        return 1

    ret = square(n, k//2)

    if k % 2 == 0:
        return (ret * ret) % p
    else:
        return (ret * ret * n) % p

top = factorial(N)
bottom = factorial(K) * factorial(N-K)

print(top * square(bottom, p-2) % p)

위에서 구했던 식 $ (N!  mod  p * ((N-K)!K!)^{p-2}  mod  p)  mod  p $을 그대로 구해주는 방식이다.

 

 

팩토리얼 함수

def factorial(n):
    ret = 1
    for i in range(2, n+1):
        ret = (ret * i) % p
    return ret

첫 시도에서 사용했던 공식 (n * (n-1) * ... * (n-k+1)) / k!를 써먹어도 되지만,
정직하게 N!과 (N-K)!, K!를 구하는 방식을 사용했다.

 

제곱 함수

def square(n, k):
    if k == 0:
        return 1

    ret = square(n, k//2)

    if k % 2 == 0:
        return (ret * ret) % p
    else:
        return (ret * ret * n) % p

제곱 문제에서 사용했던 방식이다.
지수가 짝수라면 square(n, k//2) * square(n, k//2)를, 홀수라면 n * square(n, k//2) * square(n, k//2)를 반환한다.

 

top = factorial(N)
bottom = factorial(K) * factorial(N-K)

print(top * square(bottom, p-2) % p)

top에는 N!를, bottom에는 (N-K)!K!를 할당한다.
그리고 square(n, k)함수를 통해 ((N-K)!K!)^(p-2)를 구해준다.
마지막으로 이 두 값을 곱한 후, p로 나눈값을 출력하면 끝이다.

---

이런 문제들을 만날때마다 수학 공부의 중요성을 느낀다...^^

문제집을 다시 살수도 없고 참...