[백준] 1010번 다리 놓기

💡문제접근1

조합을 이용해서 문제를 해결할 수 있다.

💡코드1(메모리 : 32540KB, 시간 : 36ms)

import sys
import math

T = int(input())
for _ in range(T):
    N, M = map(int, sys.stdin.readline().split())
    print(math.factorial(M) // (math.factorial(M-N) * math.factorial(N)))

💡문제접근2

팩토리얼의 값을 DP를 활용해서 선언한 후 이를 이용해 다리를 놓을 수 있는 경우의 수를 계산한다.

💡코드2(메모리 : 30616KB, 시간 : 36ms)

import sys

T = int(input())
dp = [0 for i in range(31)]
dp[0] = 1
for i in range(1, 31):
    dp[i] = i * dp[i-1]

for _ in range(T):
    N, M = map(int, sys.stdin.readline().split())
    print(dp[M] // (dp[M-N] * dp[N]))

💡소요시간 : 3m