[백준] 1010 - 다리놓기

https://www.acmicpc.net/problem/1010

1010번: 다리 놓기

• 실제적으로 DP를 활용할 수 있는 능력이 필요하다.
• 그 외에는 수학 공식만 알고있다면 풀 수 있다.

import sys
input = sys.stdin.readline

T = int(input())
dpDict = {}
for tdx in range(T):
    N, M = list(map(int, str(input()).split()))
    
    if(N == M): print(1)
    else:
        # r!
        rFact = 1
        if N in dpDict.keys(): rFact = dpDict.get(N)
        else:
            for r in range(1, N+1): rFact *= r

        # (n-r)!
        nrFact = 1
        if (M-N) in dpDict.keys(): nrFact = dpDict.get(M-N)
        else:
            for nr in range(1, M-N+1): nrFact *= nr

        # n!
        nFact = 1
        if M in dpDict.keys(): nrFact = dpDict.get(M)
        else:
            for n in range(1, M+1): nFact *= n
        
        print(int(nFact / (nrFact*rFact)))