BOJ-11401 이항 계수 3 Swift

문제

자연수 \(N\)과 정수 \(K\)가 주어졌을 때 이항 계수 \(\binom{N}{K}\)를 1,000,000,007로 나눈 나머지를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 \(N\)과 \(K\)가 주어진다. (1 ≤ \(N\) ≤ 4,000,000, 0 ≤ \(K\) ≤ \(N\))

출력

 \(\binom{N}{K}\)를 1,000,000,007로 나눈 나머지를 출력한다.

내가 푼 풀이

수학적 지식의 벽을 느낀 문제였다... 다른사람의 풀이를 보고 이해하는데도 오래걸렸다.

하지만 알아두면 좋을 것 같아서 이렇게 기록해둔다.

 

접근방법: 분할정복, 페르마의 소정리, 모듈러 연산, 이항계수, 지수법칙

1. 이항계수 구하기: \(\binom{N}{K}\) = ${_N}C{_K}$ =  $\frac{N!}{(N-K)! \times K!}$

 

페르마의 소정리

 

소수 $p$와 정수 $a$에 대해서  ${\displaystyle p\nmid a}$일때,

$a^{p} \equiv  a(\mathrm{mod} p)$ 이며 $a\neq 0 $ 라면

$a^{p-1} \equiv  1(\mathrm{mod} p)$ 이다.

 

${\displaystyle p\nmid a}$: a는 p의 약수가 아니다.

합동식 $\equiv$ 의 의미는 아래와 같다.

$a \equiv b (\mathrm{mod} p)$ : a를 p로 나눈 나머지와 b를 p로 나눈 나머지는 같다.

이 점을 생각해서 위 식은 $ a^{p-1}$를 $p$로 나눈 나머지와 $1$을 $p$로 나눈 나머지는 같다라고 의미한다.

 

문제에서 p는 1,000,000,007이고, 이는 소수이므로 페르마의 소정리를 이용할 수 있다.

 

${_N}C{_K}$ =  $\frac{N!}{(N-K)! \times K!}$ = $N! \times((N-K)! \times K!)^{-1}$ 로 표현 할 수 있고,

최종적으로 아래의 식을 구하면 된다.

 

정답: $(N! \times((N-K)! \times K!)^{-1}) \mathrm{mod}p $ $( p = 1,000,000,007)$

 

여기서 모듈러의 연산중 분배법칙을 적용하면 

$(N! \times((N-K)! \times K!)^{-1}) \mathrm{mod}p $ = $(N!\mathrm{mod}p \times((N-K)! \times K!)^{-1}\mathrm{mod}p)\mathrm{mod}p$

 

페르마의 소정리 를 적용하면

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

=$ a^{-1}(\mathrm{mod}p) \equiv a^{p-2}(\mathrm{mod}p)$ ( $\frac{1}{a} = a^{-1}$ 이므로)

로 나타낼 수 있다.

여기서 a 가 $ ((N-K)! \times K!)^{-1} $ 라면 

$ ((N-K)! \times K!)^{-1} $ = $ ((N-K)! \times K!)^{p-2} $ ( p = 1,000,000,007) 가 된다

 

많이왔다..

최종적으로 우리는 아래의 답을 구하면된다.

정답:  $(N!\mathrm{mod}p \times((N-K)! \times K!)^{1,000,000,007-2}\mathrm{mod}p)\mathrm{mod}p$

1,000,000,007 - 2 제곱은 단순히 실행만해도 1,000,000,005번 실행하게된다.

분할정복은 바로 제곱수를 구할때 적용한다.

지수법칙을 이용하면 다음과 같다. $x^{ab} = x^{a} \times x^{b}$

제곱수의 p-2가 1이 될때까지 분할하고, 1이되면 정복하여 해당 값을 리턴한다.

이때 모듈러의 연산에 의해 값을 리턴할 때 p로 나누어준다.

 

정말 어려웠다 이해하는것도 어려웠고 잘 이해했는지도 모르겠다.

하지만 이 같은 문제가 다시 나온다면 그래도 풀이시작을 해볼 수 있을것같다.

 

코드로 구현하면 다음과 같다.

import Foundation

// 입력
let input = readLine()!.split(separator: " ").map{Int(String($0))!}
let N = input[0], K = input[1]
let p = 1000000007
// 팩토리얼 계산
// 0! = 1이다. 4! = 4 * 3 * 2 * 1 = 4 * 3!으로 나타냄
// 이와같이 1!을 표현하면 1! = 1 * 0!이다. 따라서 0! = 1
func factorial(_ num: Int)-> Int {
    var n = 1
    if num <= 1 { return 1}
    
    for i in 2...num {
        n = n * i % p
    }
    return n
}
// 분할 정복
func divide(_ n: Int,_ k: Int) -> Int{
    // 지수가 1이 되면 값 리턴 (정복)
    if k == 1 { return n % p}
    // 분할
    let m = divide(n, k/2)
    
    // 지수가 1이될때까지 분할한다.
    // 지수가 짝수면 몫*2로 딱 나누어떨어지지만
    // 지수가 홀수면 몫 , 몫+1이 되므로 짝수에서 값을 한번더 곱해준다.
    if k % 2 == 0 {
        return m*m%p
    } else {
        return (m*m%p)*n%p
    }
    
}
// 출력
print(factorial(N) * divide(factorial(N-K) * factorial(K) % p, p-2) % p)