[백준] 11401. 이항 계수 3/Python - Gold1

❓문제

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

성능 요약

메모리: 32412 KB, 시간: 872 ms

문제 설명

자연수 N과 정수 K가 주어졌을 때 이항 계수 (N K)를 1,000,000,007로 나눈 나머지를 구하는 프로그램을 작성하시오.

✍🏻풀이

페르마의 소정리를 이용해야지 풀리는 문제이다.
페르마의 소정리는 MOD가 소수일 때 a^p = a % p를 의미하며, 양변을 a²으로 나누면 a^(p-2) = 1 / a % p가 된다.

💻코드

import sys

input = sys.stdin.readline
MOD = 1000000007

def fact(N):
    if N <= 1:
        return 1

    res = 1
    for i in range(2, N+1):
        res *= i
        res %= MOD

    return res

def col(N, K):
    if K == 0 or N == K:
        return 1
    if K == 1:
        return N

    res = col(N, K//2)
    if K%2 == 0:
        return res * res % MOD
    else:
        return res * res * N % MOD

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

num = fact(N)
den = fact(K) * fact(N - K)

print(num * col(den, MOD - 2) % MOD)

📍후기

분할정복 문제라고 해서 파스칼 삼각정리 생각해서 작성했는데 메모리 초과 ... ㅎㅎ역시 골드 문제는 다르다...