166. 다리 놓기

백준

1. Python

import math

T = int(input())

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

T = int(input())

for _ in range(T):
    m, n = map(int, input().split())
    answer = 1
    k = n - m
    
    while n > k:
        answer *= n
        n -= 1
    while m > 1:
        answer = answer // m
        m -= 1
    
    print(answer)

def combination(n,r):
    if dp[n][r] != 0:
        return dp[n][r]
    if r == 1:
        return n
    elif n == r:
        return 1
    else:
        dp[n][r] = combination(n-1, r) + combination(n-1, r-1)

    return dp[n][r]


r,n = map(int, input().split())
dp = [ [0 for _ in range(r+1)] for _ in range(n+1)]
ans = combination(n,r)
print(ans)