[Algorithm] 백준 11401번: 이항 계수 3 | 페르마의 소정리, 약수의 나머지 곱을 통한 나머지 연산

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

---

1. 결과

메모리 188804KB, 시간 1144ms

2. 풀이

이 문제를 처음에 풀이할 때는 혼란스러웠다. 분할 정복과 재귀 호출 등을 사용해서 팩토리얼 연산 횟수를 최대한 줄이는 것이 문제의 요점이라고 생각했다. 하지만 그렇게 풀이한 코드는 채점 결과 런타임 에러를 발생했고, 생각해보면 최대 400만 번의 재귀 호출이 발생할 수 있기 때문에 납득할 수 있는 결과였다. 하지만 그렇다면??

어떤 풀이로 접근을 해야 할지 고민을 하며 다른 블로그와 풀이 아이디어만을 참고하려고 검색하던 중 '페르마의 소정리'를 이용하는 문제라는 것을 알았다. 페르마의 소정리란 코드의 주석 부분에 작성한 것처럼 소수인 p와 그 p의 배수가 아닌 A에 대해 A^(p-1)을 p로 나눈 나머지가 1이 된다는 정리였다.

이를 어떻게 적용시킬 수 있을까 생각하던 중에 이항 계수를 계산하기 위해선 분자에 N!, 분모에 K! * (N-K)!이 온다는 것을 생각했다. 여기서 A = N!, B = K! * (N-K)!이고, A * B^(-1)이 이항 계수의 값이었다. 그리고 이를 P(1,000,000,007)로 나누어야 하기 때문에 {( A % P ) * ( (B^-1) % P )} % P를 구하면 되는 문제로 바꿀 수 있었다. 여기서 큰 수의 나머지를 구하는 공식은 아래와 같다.

( A * B ) % P = ( ( A % P ) * ( B % P ) ) % P

이런 방식으로 나머지를 구할 수 있는데, 쉽게 말해 어떤 큰 수의 나머지는 그 수의 약수에 계산한 나머지끼리 곱한 값과 같다는 의미이다.

어쨌든 페르마의 소정리를 응용해서 정수끼리의 나눗셈을 정수끼리의 곱셈으로 변환하여 처리하는 것이 요점인 문제였다.

그리고 조금 의아했던 것은 팩토리얼의 값을 그냥 for문으로 각 인덱스에 해당하는 팩토리얼 값을 저장하는 리스트로 계산 및 구현했다는 점이다. 여전히 재귀 호출로 팩토리얼을 구하는 것에서 오류가 발생했는데, 다른 풀이를 참고하니까 반복문을 통해 구하고 있었다. 아마 문제의 조건이나 채점 기준에서 재귀 호출의 횟수를 제한했기 때문에 발생한 오류가 아니었을까 싶다. 또, 어떻게 보면 동적 계획법을 이용한 팩토리얼 연산이므로 이 경우에서는 A와 B에 대해 각각 재귀 호출을 하며 중복되는 연산 횟수만큼 낭비하는 것보다는 시간 측면에서도 최소 3배는 빠를 것이기 때문에 효율적이라는 생각이 든다. 이처럼 각 문제에 대해 구현 방법 또한 무조건 어떤 것은 맞고, 어떤 것은 틀리다고 생각하는 것보단 각 상황에 따라 귀찮더라도 여러 방법을 모색해보고 도전해보는 것이 좋을 것 같다.

import sys

# 페르마의 소정리 이용
# 소수인 p, p의 배수가 아닌 A에 대해 A^(p-1) === 1(mod p) - p로 나눈 나머지가 1
# 즉, (A^(p-2))%p = (A^(-1))%p
# 이를 이용해서 이항 계수의 분모로 인한 나눗셈을 곱셈으로 변환
def fermaPower(b, p, origin_p):
    if p == 1: return b % origin_p
    elif p % 2: return (b * (fermaPower(b, p//2, origin_p) ** 2)) % origin_p
    else: return (fermaPower(b, p//2, origin_p) ** 2) % origin_p

def main():
    P = 1000000007
    N, K = map(int, sys.stdin.readline().split())
    # 재귀함수로 생성하면 재귀 반복 최대 횟수 초과 오류 발생
    factorialList = [1 for _ in range(N+1)]
    for i in range(2, N+1):
        factorialList[i] = (i * factorialList[i-1]) % P
    A, B = factorialList[N], (factorialList[K] * factorialList[N-K]) % P
    return ((A%P) * (fermaPower(B, P-2, P)%P)) % P

if __name__ == "__main__": print(main())