[1010] 다리놓기 in python

> 다이나믹

> 조합

 

 

 

일단 조합으로 먼저 푼 문제

 

해당 문제는 서로 다리가 교차되는 일은 허용되지 않으므로

순열(중복허용)대신 조합(중복불허)을 사용함.

 

 

 

조합은 팩토리얼 함수를 이용해서 구할 수도 있고,

permutation 함수를 이용할 수도 있음.

 

해당 문제에서는 팩토리얼을 재귀함수로 구현

 

ex) 6C3 = 6 * 5 * 4 // 3!

8C3 = 8 * 7 * 6 // (3!)

-> 

( factorial(8) // factorial(8-3) ) // factorial(3)

t=int(input())
def factorial(n):
    if n==0 or n==1:
        return 1
    return factorial(n-1)*n
for _ in range(t):
    w,e=map(int,input().split())
    result=(factorial(e)//factorial(e-w))//factorial(w)
    print(result)

---

# 2 . 팩토리얼 구하는 걸 DP를 사용 

 

# 2. dp
t = int(input())
dp = [0 for _ in range(31)]
for i in range(31):
    if i == 0 or i == 1:
        dp[i] = 1
        continue
    dp[i] = dp[i - 1] * i
for _ in range(t):
    w, e = map(int, input().split())
    result=(dp[e]//dp[e-w])//dp[w]
    print(result)
'''
# 1 factorial 구현
t=int(input())
def factorial(n):
    if n==0 or n==1:
        return 1
    return factorial(n-1)*n
for _ in range(t):
    w,e=map(int,input().split())
    result=(factorial(e)//factorial(e-w))//factorial(w)
    print(result)
'''