#1010

처음에는 지금 어디까지 다리가 만들어졌는지 기억하면서 반복문을 돌아야 하나? 라는 생각을 했다.

1부터 N까지, 1부터 M까지 숫자를 대입해서 상황을 그려봤는데 조합으로 구하면 된다는 걸 알았다.

처음 짠 코드

from itertools import combinations

for i in range(int(input())):
    N, M = map(int, input().split())
    
    items = [ j for j in range(1, M+1)]
    combiItemsBy3 = list(combinations(items, N))
    # print("combiItemsBy3 = ", combiItemsBy3)
    print(len(combiItemsBy3))

시간 초과가 나왔다. 이 문제에서는 모든 조합의 경우의 수 하나하나는 필요없고 몇가지가 있을 수 있냐? 의 수만 구하면 되기 때문에

itertools 라이브러리를 이용해서 조합을 구하면 시간초과가 나온다. 공식을 이용해서 몇 가지의 경우의 수가 나올 수 있는지만 구하면 된다.

정답 코드

def factorial(n):
    total = 1   
    for i in range(n, 1, -1):
        total *= i
    return total


for i in range(int(input())):
    N, M = map(int, input().split())
    
    answer = 0
    answer = factorial(M) // (factorial(N) * factorial(M-N))
    print(answer)