[Python] BOJ 11051 이항 계수2

출처 : 백준

이 문제를 처음엔 자바로 풀려고 했지만 12! 이 넘어가면 int 형을 초과하고 20! 을 넘어가면 long 형을 초과하여 엉뚱한 숫자가 튀어나온다. 이를 해결하기 위해선 모듈러 증명과 페르마의 소정리에 대한 수학적 지식이 있어야 알고리즘으로 접근할 수 있다. 

 

정석으로 풀기 위해선 이분 블로그를 참고하면 좋을 것 같다.

https://st-lab.tistory.com/162

[백준] 11051번 : 이항 계수 2 - JAVA [자바]

 

필자의 포스팅에선 자바가 아닌 파이썬으로 이를 해결한 과정을 포스팅 하고자 한다.

 

이에 앞서 자바나 C++ 과 같이 변수의 크기를 지정해주거나 데이터 타입을 명시해줘야 하는 언어와는 달리 파이썬 3에서는 long 타입이 없어지고 int 타입만 남았는데, 이 int가 arbitrary precision을 지원하여 데이터 타입의 오버플로우가 발생하지 않는다. 

arbitrary precision
In computer science, arbitrary-precision arithmetic, also called bignum arithmetic, multiple precision arithmetic, or sometimes infinite-precision arithmetic, indicates that calculations are performed on numbers whose digits of precision are limited only by the available memory of the host system
-Wikepedia

arbitrary precision은 쉽게 말해 메모리를 미리 정해놓지 않고 컴퓨터의 사용 가능한 메모리를 필요할 때 가져다 쓰는 것이다. 그러니까 수가 엄청나게 커져도 컴퓨터의 메모리가 허락하는 한 오버플로우가 발생하지 않는다.

 

파이썬 코드는 다음과 같다.

a,b = map(int, input().split())

def factorial(n,m):
    sum = n
    for i in range(m-1):
        n-=1
        sum *= n
    return sum

def r_factorial(n):
    if n==0:
        return 1
    sum = 1
    for i in range(n,1,-1):
        sum *= i
    return sum

print(int((factorial(a,b)//r_factorial(b)))%10007)

우리가 흔히 이항 계수를 계산할 때 예를 들어 5C2라고 한다면, 분자는 5 * 4, 분모는 2! 이 된다. 분자는 5에서 시작해 2번의 팩토리얼 연산을 진행한다. 

 

aCb라고 하면, a*(a-1)*(a-2)*...(a-(a-b)+1) / b! 인 것을 그대로 구현한 코드이다. 단, 분자와 분모를 나누어 줄 때 int/int 는 float 형이 되기 때문에 부동소수점 에러가 발생할 수 있어서 int // int로 해주어야만 정상적인 값이 나온다.