[백준알고리즘] 11401번: 이항 계수 3 -Python

[백준알고리즘] 11401번: 이항 계수 3 -Python

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

11401번: 이항 계수 3

어렵다.. 처음에 풀다가 방법을 찾아봤다

그러다가 "페르마의 소정리"와 "확장 유클리드 호제법"으로 해결이 가능하다는 것을 확인하고 공부했던 내용을 다시 확인했다. 

 

우선 "확장 유클리드 호제법"을 확인하고 해당 방법으로 문제를 해결했다. 이전에 공부했던 내용이라 다른 분의 블로그를 참조하니 이해가 쉬웠다. 해당 블로그의 링크는 아래이며 이해가 안되면 더 찾아보면 될 것 같다.

https://joonas.tistory.com/25#

 

간단히 정리하자면 N*(N-1)...*(N-K+1)까지 모듈로 연산을 수행하고, K*(K-1)...*1까지의 모듈로 연산을 수행했다. 그 후 K! 에 해당하는 모듈로 값의 역원을 구해서 풀었다. 이 역원을 구하는 과정에 확장 유클리드 호제법을 사용하게 된다. s, t, r, q를 이용해 풀고 역원이 음수 값이 나오게 되면 p값을 더해서 양수로 만들어주었다.

 

코드는 아래와 같이 정직하게 했다.

import sys

N, K = map(int, sys.stdin.readline().split())
mod = 1000000007

def find(kResult):
    s1, s2 = 1, 0
    t1, t2 = 0, 1
    r1, r2 = kResult, mod
    q = r1//r2
    
    while r1%r2 != 0:
        r = r1%r2
        r1, r2 = r2, r
        s1, s2 = s2, s1 - s2*q
        t1, t2 = t2, t1 - t2*q
        q = r1//r2

    return (lambda x: x if x > 0 else x + mod)(s2)


def getResult(n, k):
    nResult = 1
    kResult = 1
    
    for i in range(k):
        nResult *= ((n-i) % mod)
        nResult %= mod
        kResult *= ((k-i) % mod)
        kResult %= mod
    
    # find inverse to K!
    kResult = find(kResult)

    return (nResult * kResult) % mod

sys.stdout.write(str(getResult(N, K)) + "\n")

 

풀고나서 다른 분들의 코드를 확인했는데 대부분이 "페르마의 소정리"를 이용해서 풀었고 이 방법이 이해만 한다면 코드를 짜기 더 간단해 보였다. 또 실제 측정된 속도가 더 빠른 경향이 있는 것 같다.

페르마의 소정리는 여기를 보고 복습했다..

 

사실 저 링크만으로는 어떻게 풀지 몰랐는데 질문에 있는 글이 도움이 많이 됐다. 사실 거의 다 알려준 것 같다.

 

간단하게 정리하면 소수인 p와 p의 배수가 아닌 a에 대해서 a^p mod p = a mod p이며 a^(p-1) mod p = 1 mod p이기 때문에 (a * a^(p-2)) mod p = 1 mod p가 되어 a의 역원이 a^(p-2)라는 사실을 이용하는 것이다. 따라서 위에 해결했던 코드를 그대로 이용해도 결국에 역원을 구하는 과정만 다르게 되는 것이다.

 

a^(p-2) mod p를 구할 때에는 빠른 모듈로 거듭제곱을 이용하면 빠르게 구할 수 있기 때문에 거기에 도가 튼 사람들이 많은 것 같다..... 이 방법으로 푼 사람들의 코드는 문제를 해결하면 많이 보이고 테크닉들이 장난이 아니기 때문에 직접 확인하는 것이 좋을 것 같다.

 

 

잘못된 점이나 부족한 점 지적해주시면 감사하겠습니다