이항계수 [백준 11401] - python

import sys
input = sys.stdin.readline
prime = 1_000_000_007


def BOJ11401():
  def factorial(n):
    ans = 1
    for i in range(1, n+1):
      ans = (ans * i) % prime 
    return ans

  def pow(a, b):
    if b == 1:
      return a
    elif b % 2 == 0:
      return (pow(a, b//2) ** 2) % prime
    else:
      return (pow(a, b//2) ** 2) * a % prime
         
  N, K = map(int, input().split())

  A = factorial(N)
  B = (factorial(K) * factorial(N-K))
  print((A % prime * (pow(B, prime-2)) % prime) % prime)

BOJ11401()

 

접근방법 :

  1. 나누는 숫자가 굉장히 크고 N의 범위 상당히 크다. 파스칼 삼각형을 이용하여 nCk 에 접근할수도 있지만 N^2 * 4Byte의 공간복잡도를 가지게 되어 제한 메모리 256MB를 초과하게 된다. 
메모이제이션 + 팩토리얼 계산으로 값에 접근할수도 있지만 이렇게 되면 분모가 0이 될수도 있어 값이 틀려지게 된다.

 => nCk = n! / (n-k)!k!

 

 2. 페르마의 소정리를 이용하였다. 아래의 내용에서 파악할 수 있다

   (a로 나눠주는것은 a의 역수를 곱해주는 것과 같다.)

 

 

 

장애물 이였던 것 :

  1. 풀지 못했던 문제이고 다른분들의 풀이를 참고했다.

  2. 페르마의 소정리를 이용하여 풀어야 한다. 차근차근 설명해보자

페르마의 소정리 

a^p-1 = 1 (mod P)   (a와 p는 서로소이다)   
a의 p-1제곱을 p로 나눈 나머지 값은 1이다
ex) 64^70 =1 (mod 71)  => 64의 70제곱을 71로 나눈 나머지 값은 1이다.

 

 

 

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

11401번: 이항 계수 3