[백준] 1010번 다리 놓기 (파이썬)

이 문제를 해결하는 데는 두 가지 방법이 존재함.

 

두 문제에 공통적으로 사용되는 요소는 조합.

 

조합 = 서로 다른 n개 중에 r개를 선택하는 경우의 수 의미.

 

${}_nC_r = {n! \over (n-r)!r!}$

 

1. 다이나믹 프로그래밍 적용 X

def factorial(N):
    if N > 1:
        return (N * factorial(N-1))
    else:
        return 1

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

 

2. 다이나믹 프로그래밍 적용 O

T = int(input())
dp = [[0] * 30 for _ in range(30)]
for i in range(30):
    for j in range(30):
        if i == 1:
            dp[i][j] = j
        else:
            if i == j:
                dp[i][j] = 1
            elif i < j:
                dp[i][j] = dp[i-1][j-1] + dp[i][j-1]

for _ in range(T):
    N, M = list(map(int, input().split()))
    print (dp[N][M])