[백준] 1010번 다리놓기

💡 문제접근1

조합론을 이용하여 다리를 놓을 수 있는 모든 경우의 수를 계산한다.

💡 코드1

from math import factorial

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

💡 문제접근2

DP를 이용하여 문제를 해결한다.

💡 코드2

dp = [0] * 31
dp[0] = 1
for i in range(1, 31):
    dp[i] = i * dp[i-1]		# dp를 이용해 팩토리얼 값을 저장

T = int(input())
for i in range(T):
    N, M = map(int, input().split())
    print(dp[M] // (dp[N] * dp[M-N]))