[BOJ] 11051번 이항 계수2 / 사용언어 : 파이썬(python)

※ 문제링크

11051번: 이항 계수 2

 

해당 문제는 조합론과 스택오버플로우와 관련된 문제였다. 이항계수를 구하는 식을 재귀함수로 그대로 사용하게 되면 사용하는 숫자가 너무 커져서 완전히 다른 값을 반환하기에 중간에 숫자의 크기를 줄일 수 있게 약분을 해준 후 최종적으로 결과값을 산출해야 하는 문제였다. 문제를 해결한 방법과 코드는 아래와 같다.

1. 팩토리얼 함수를 만들때 결과값이 아닌 곱해야하는 값들을 리스트 값으로 만들어 반환하도록 한다.

2. 반환한 리스트 함수들을 반복문을 통해 공통 약수들은 모두 약분해준다.

3. n!이 k!(n-k)! [단, k <= n]는 성질을 이용하여 //로 몫을 구한 후 10007로 나눈 나머지값을 반환한다.

+ 추가적인 시간 단축을 위해서 메모이제이션 방식으로 함수를 구성해보았다.

 

factorial_memo = {}
def factorial(number):
    r_list = []
    if number < 2:
        return [1]
    if number not in factorial_memo:
        r_list = [i for i in range(2, number+1)]
        factorial_memo[number] = r_list
    return factorial_memo[number]
    
N, K = map(int, input().split())
r_N = factorial(N)[:]
r_K = factorial(K)[:] + factorial(N-K)[:]
check = 2
while check <= len(r_N):
    if check in r_N and check in r_K:
        r_N.remove(check)
        r_K.remove(check)
    check += 1
value = 1
for num in r_N:
    value *= num
for num in r_K:
    value //= num # n!은 k!(n-k)! 정확히 나누어 떨어짐
print(value % 10007)

 

P.S 개발자가 되기위해 공부중입니다. 잘못된 부분을 댓글로 남겨주시면 학습하는데 큰 도움이 될 거 같습니다.