[python3] 백준 11050번 - 이항 계수 1

문제

문제에서 주어지는 두 수 N, K를 이용해 이항 계수 $ \binom{n}{r} $ 즉, $ _nC_r $ 을 구하는 문제이다.

Combination의 정의인 $ _nC_r = \frac{n!}{(n-r)!r!} $ 을 이용해서 풀 수도 있겠지만, 이전에 올렸던 이항 계수의 성질을 이용하면 훨씬 빠르고 효율적으로 구할 수 있다.

2024.07.20 - [BOJ/이론] - 조합(Combination)과 이항 계수를 python으로 구현해보자.

조합(Combination)과 이항 계수를 python으로 구현해보자.

위 성질을 이용하지 않고 다음과 같이 Combination의 정의를 사용해서 코드를 제출하면, 재귀함수가 너무 깊어져서 발생하는 에러인 런타임 에러 (RecursionError)가 발생하게 된다.

def combi(a):
    if a==1: return 1
    return a*combi(a-1)
    
n,k = map(int, input().split())
print(int(combi(n)/(combi(k)*combi(n-k))))

위처럼 구현하면 n이 커지면 O(n!)의 시간복잡도를 가지기 때문에, sys.setrecursionlimit()를 통해 재귀함수의 최대 깊이를 변경해도 웬만큼 크게 잡아서는 똑같이 런타임 에러 (RecursionError)가 나고, 이를 해결한다 하더라도 시간 초과가 나게 된다.

코드

다음과 같이 코드를 구현하자.

def combi(n, k):
    if k==0 or n==k:
        return 1
    return combi(n-1,k) + combi(n-1,k-1)
    
n,k = map(int, input().split())
print(combi(n,k))

이전과 다르게 빠르게 계산 결과과 나오며 정답인 것을 확인할 수 있다.