백준 11401번: 이항 계수 3 [python]

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

문제 접근

이항 계수 (N, K) = N! / K!(N-K)! 으로 구할 수 있다.
이를 1,000,000,007로 나눈 값을 구하는 문제이다.

나눗셈에서의 모듈러 연산: 페르마의 소정리

• 일반적으로 (A / B) % P 는 계산할 수 없다.
• 대신 B의 모듈러 역원을 곱해서 해결한다.

A / B % P = A * B^(P-2) % P  (단, P는 소수여야 함)

코드 및 풀이

import sys
input = sys.stdin.readline

MOD = 10**9 + 7  # 문제에서 주어진 소수

# 거듭제곱을 빠르게 계산하는 함수 (a^b % MOD)
def power(a, b):
    result = 1
    while b > 0:
        if b % 2 == 1:
            result = (result * a) % MOD
        a = (a * a) % MOD
        b //= 2
    return result

# 입력
N, K = map(int, input().split())

# 1부터 N까지의 팩토리얼을 미리 계산
factorial = [1] * (N + 1)
for i in range(1, N + 1):
    factorial[i] = (factorial[i - 1] * i) % MOD

# 분자: N!
numerator = factorial[N]

# 분모: K! * (N-K)!
denominator = (factorial[K] * factorial[N - K]) % MOD

# 페르마의 소정리를 이용해 분모의 역원 구하기
inv_denominator = power(denominator, MOD - 2)

# 최종 결과
print((numerator * inv_denominator) % MOD)

핵심 요약

• 이항 계수는 N! / (K! * (N-K)!) 로 계산됨
• 나눗셈이 안 되므로, 역원을 구해 곱해줌 (페르마의 소정리 사용)
• 팩토리얼은 미리 계산하고, 빠른 제곱으로 역원 구함