백준 1010번: 다리 놓기 (Python)

처음에 봤을 때 막막했는데 경우의 수를 나열했을 때 익숙한 숫자 배열이여서 조합인걸 알았다. 그래서 조합을 사용해서 코드를 짜 봤는데,

import itertools

N = int(input())

for i in range(N):
    a, b = map(int, input().split())
    nCr = itertools.combinations([f"{i}" for i in range(b)], a)
    print(len(list(nCr)))

오른쪽 다리의 최대 갯수가 30개인걸 생각하면 조합을 사용해서는 시간 초과가 나올 것이 분명해서 그냥 식을 써봤다.

import sys
sys.getrecursionlimit = 1000000

N = int(input())

def nCr(n, r):
    return (fac(n) // fac(r)) // fac(n-r) 

def fac(num):
    if num <= 1: return 1
    return fac(num - 1) * num

for i in range(N):
    a, b = map(int, input().split())
    print(nCr(b, a))

nCr = n! / (n-r)! * r! 이니 그대로 옮겨서 함수로 구현해 봤다.

맞았다