[백준 알고리즘] 1010번 다리 놓기. 파이썬(python)

m개 중 n개를 순서 상관없이 고른다. → 조합문제

from itertools import combinations

T=int(input()) 

for _ in range(T):
    n,m=map(int, input().split())
    arr=[0]*m
    print(len(list(combinations(arr,n))))

# 배열을 만든 이유
# combinations는 배열 중에 n개를 뽑는다는 의미->(arr,n)
# n개를 뭘 뽑았는지 리스트 형식으로 저장하고 개수를 세기 위해 길이를 출력

정답은 맞지만 n, m이 커질수록 시간이 너무 오래 걸려 시간초과가 일어난다.

그래서 팩토리얼 함수를 만들어 조합 공식에 대입한다.

T=int(input()) 

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

for _ in range(T):
    n,m=map(int, input().split())
    result=factorial(m)//(factorial(m-n)*factorial(n))
    print(result)