[백준11401] 이항 계수 3

 

 

---

<문제해석>

1. 이항 계수의 정의

 

2. 출력값

 

 

 

3. 문제

1. 큰 수의 계산:
   • N과 K가 최대 4,000,000이므로, 팩토리얼을 계산하면 값이 매우 커짐. 예를 들어, 4,000,000!은 수가 너무커서   오버플로우가 발생.
2. 나눗셈 모듈러:
   • 이항 계수를 계산할 때 나눗셈을 수행해야 한다. BUT, 모듈러 연산에서는 나눗셈이 직접적으로 허용되지 않기   때문에 모듈러 역원을 사용.  (추후 모듈러 역원에 대해서 글 작성, 귀찮으면 안할수도,,,,)

=> 이 문제를 극복하기 위해 모듈러 연산과 페르마의 소정리를 활용하여 해결 가능.

---

코드 

import sys
input = sys.stdin.readline

N, K = map(int, input().split())
p = 1000000007

# 이항 계수 C(N, K) 계산
def binomial_coefficient(N, K):
    if K > N:
        return 0  # K가 N보다 클 경우는 0
    if K == 0 or K == N:
        return 1  # C(N, 0) 또는 C(N, N)은 1

    numerator = 1
    denominator = 1

    # 분자: N * (N-1) * ... * (N-K+1)
    for i in range(K):
        numerator = (numerator * (N - i)) % p
        denominator = (denominator * (i + 1)) % p

    # 페르마의 소정리를 이용하여 분모의 모듈러 역원 계산
    denominator_inverse = pow(denominator, p - 2, p)

    return (numerator * denominator_inverse) % p

# 결과 출력
print(binomial_coefficient(N, K))

 

---

코드 설명

• 이항계수 계산 함수: C(N,K) 계산

def binomial_coefficient(N, K):
    if K > N:
        return 0  # K가 N보다 크면 조합이 성립하지 않으므로 결과는 0
    if K == 0 or K == N:
        return 1  # C(N, 0)과 C(N, N)은 항상 1

 

 

• 분자와 분모 계산

    numerator = 1
    denominator = 1

    for i in range(K):
        numerator = (numerator * (N - i)) % p 
        denominator = (denominator * (i + 1)) % p

 

 

numerator는 이항 계수 분자의 값을 계산: N×(N−1)×⋯×(N−K+1)

denominator는 이항 계수 분모의 값을 계산: K!=1×2×⋯×K

 

• 모듈러 역원 계산과 최종 결과

    # 페르마의 소정리를 이용하여 분모의 모듈러 역원 계산
    denominator_inverse = pow(denominator, p - 2, p)

 

 

a^(p−1)≡1(mod p)이므로 a^(p−2)≡a^(−1) (mod p)

즉, 역원 구해짐.

 

    return (numerator * denominator_inverse) % p

 

 

나눗셈을 곱셈으로 형태 바꿔줌

 

• 모듈러 역원 계산과 최종 결과

print(binomial_coefficient(N, K))