📘[백준-1010] 다리놓기(Python)

[백준-1010] 다리놓기 Python해답과 에러

백준/단게별 문제/조합론/다리놓기 문제를 풀어보았다.

중복이 불가능한 뽑기 라고 생각해서 가장 먼저 이항계수($_nC_r$)를 떠올렸다.

코드

정답코드

import sys

def m_C_n(n, m):
    up = 1
    down = 1

    for i in range(m, m-n, -1):
        up *= i
    for i in range(1, n+1):
        down *= i
    
    return round(up/down)
        
num = int(sys.stdin.readline())
result = []
for i in range(num):
    n, m = map(int, sys.stdin.readline().split())  

    result.append(m_C_n(n, m))

for i in range(num):
    print(result[i])

에러코드

def factorial(n):
    if n == 1:      
        return 1    
    return n * factorial(n-1)    

n = int(input())
m = int(input())

print(factorial(n)/(factorial(m)*factorial(n-m)))

위 코드는 에러가 발생했다.
기존 공식을 적용하기 위해서 팩토리얼 계산과 재귀 방식을 사용했는데 아래와 같은 에러 메시지가 출력되면서 실행이 중단되었다.

RecursionError: maximum recursion depth exceeded

위 에러 메시지는 프로그래밍 언어나 시스템에서 허용하는 최대 재귀 깊이(recursion depth)를 초과했습니다.라는 뜻으로, 입력값에 의한 재귀 횟수가 너무 많으면 저런 에러가 발생한다.

해결 방법으로는 재귀 형식 -> 반복문 형식과, 재귀 호출의 반환값을 저장 혹은 스택 자료구조를 사용하는 방법 등이 있다.

이항계수($_nC_r$)란?

이항계수(Binomial Coefficient)는 조합론에서 등장하는 개념으로 주어진 크기 집합에서 원하는 개수만큼 순서없이 뽑는 조합의 가짓수를 일컫는다.

쉽게 생각하면 $_nC_r$에서 n부터 r개의 수까지 1만큼 감소하면서 곱한 값이 분자, r!가 분모 라고 생각하고 계산하면 쉽게 계산할 수 있다.