(Silver1)백준 11051 이항 계수 2 (Python)

문제링크

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

문제

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

입력

첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ K ≤ N)

출력

이항계수를 10,007로 나눈 나머지를 출력한다.

풀이과정

• 이항계수, 파스칼의 삼각형에 관련된 문제
  https://shoark7.github.io/programming/algorithm/3-ways-to-get-binomial-coefficients

• 기본적인 DP 유형 연습문제

• 파이썬 자체 모듈로도 풀 수 있지만 재귀에 친숙해지기위해 탑다운 방식으로 풀었다.

정답코드

재귀를 사용한 풀이

import sys

MOD = 10007
sys.setrecursionlimit(10 ** 7)

# 이미 계산한 값은 캐싱하여 기록하기 위해 리스트 생성
cache = [[0] * 1001 for _ in range(1001)]
N,K = map(int, input().split())

def bino(n,k):
	# 이미 캐싱된 값은 연산에서 제외
    if cache[n][k]:
        return cache[n][k]
    
    if k == 0 or k == n :
        cache[n][k] = 1
    else : 
        cache[n][k] = bino(n-1, k-1) + bino(n-1, k)
        cache[n][k] %= MOD 


    return cache[n][k]

print(bino(N,K))

파이썬 내의 팩토리얼 메서드를 활용한 풀이

import sys 
from math import factorial
input = sys.stdin.readline
N, K = list(map(int, input().split()))

result = factorial(N) // (factorial(K) * factorial(N-K))
print (result % 10007)

파이썬 내의 comb 메서드를 활용한 풀이(이항정리 = n개중 k를 뽑은 조합을 뽑는 것이므로)

import math

n, k = list(map(int, input().split()))
print(int(math.comb(n, k)%10007))