[백준] 11401번 : 이항 계수 3 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트

 

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

 

1. 문제 설명

반응형

2. 풀이과정

해당 문제는 이항 계수를 구하는 식 N! / (N - K)! * K! 을 1,000,000,007로 나눈 나머지를 구하는 문제이다.

문제를 해결하기 위해서는 나머지 연산의 분배 법칙과 페르마의 소정리를 활용한다.

분배 법칙은 (A x B) % p = ((A % p) X (B % p)) % p이다.

페르마의 소정리는 p가 소수일 때 a^p = a % p를 의미하며, 양 변을 a^2로 나눠주면 a^(p - 2) = 1/a % p 가 된다.

이를 활용하기 위해 N! / (N - K)! * K! 식을 곱셈으로 정리하면, N! * (N - K)! ^ -1 * K! ^ -1로 변환할 수 있고 이를 1,000,000,007로 나눈 나머지를 구하려면 N! % 1,000,000,007 * (N - K)! ^ (1,000,000,007 - 2) * K! ^ (1,000,000,007)로 나타낼 수 있다.

1,000,000,007을 편의상 p로 정리하면 N! % p * (N - K)! ^ (p - 2) * K! ^ (p - 2)로 정리할 수 있다.

팩토리얼 연산을 할 때도 분배 법칙을 바로 적용하여 연산에서 팩토리얼 결과를 1,000,000,007로 나눈 결과로 구한다.거듭제곱 연산은 이전에 해결했던 1629번 : 곱셈 문제의 거듭제곱 연산을 참조한다.

 

1. sys.stdin.readline() 함수를 사용하기 위해 sys 모듈을 불러온다. import sys
2. 각 N과 K를 입력받는다. N, K = map(int, sys.stdin.readline().split())
3. 1,000,000,007을 편의상 p로 정의한다. p = 1000000007
   
4. 이항 계수를 구할 때 필요한 팩토리얼 연산을 수행하는 함수를 생성한다. def factorial(n)
   1. 팩토리얼 결과를 저장할 변수를 생성하고 1로 초기화한다. result = 1
   2. 2부터 구할 팩토리얼 수까지 반복하며 이전 결과에 다음 수를 곱하고 p로 나눈 값을 결과에 다시 저장한다. for i in range(2, n + 1): result = (result * i) % p
   3. 최종적으로 구해진 팩토리얼 연산 결과를 반환한다. return result
5. 거듭제곱 연산을 수행하는 함수를 생성한다. def col(n, k)
   1. 만약 지수가 0이면 1을 반환한다. if (k == 0): return 1
   2. 만약 지수가 1이면 해당 수를 반환한다. if (k == 1): return n
   3. 지수가 2 이상이면 지수를 2로 나눈 몫을 가지고 거듭제곱 연산을 다시 수행한다. result = col(n, k // 2)
   4. 만약 지수가 짝수이면 거듭제곱 연산의 결과를 그대로 2번 곱해 p로 나눈 나머지를 반환한다. if (k % 2 == 0): return result * result % p
   5. 반면에 지수가 홀수이면 거듭제곱 연산의 결과를 2번 곱하고 해당 수를 한 번 더 곱해 p로 나눈 나머지를 반환한다. else: return result * result * n % p
6. 이항 계수 연산에서 분자를 계산하고 top = factorial(N)
7. 이항 계수 연산에서 분모를 계산한다. bottom = factorial(N - K) * factorial(K) % p
8. 분자는 그대로 사용하고 분모는 곱셈으로 바꿔 곱하고 p로 나눈 나머지를 구한다. answer = top * col(bottom, p - 2) % p
9. 구한 결과를 출력한다. print(answer)

3. 소스코드

import sys

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

def factorial(n):
    result = 1
    for i in range(2, n + 1):
        result = (result * i) % p

    return result

def col(n, k):
    if (k == 0):
        return 1
    
    if (k == 1):
        return n
    
    result = col(n, k // 2)
    if (k % 2 == 0):
        return result * result % p
    else:
        return result * result * n % p

top = factorial(N)
bottom = factorial(N - K) * factorial(K) % p
answer = top * col(bottom, p - 2) % p
print(answer)