[백준/python] 1010번: 다리놓기

문제

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

예시

코드

def nCr(n, r):
    if n == 1:
        return 1
    elif n == r or r == 0:
        return 1

    else:
        if dp[n][r] == -1:
            dp[n][r] = nCr(n - 1, r) + nCr(n - 1, r - 1)
        return dp[n][r]

T = int(input())

for _ in range(T):
    n, m = list(map(int, input().split()))
    dp = [[-1 for j in range(n + 1)] for i in range(m + 1)]
    print(nCr(m, n))

설명

오른쪽 포인트가 m개, 왼쪽 포인트가 n개 있고, n개의 선을 겹치지 않게 그려야하는 상황이다

즉, 오른쪽 m개의 포인트에서 n개의 포인트가 도착할 n개의 포인트를 뽑아야한다

m개 중에서 n개를 뽑아야하고 순서는 상관없다. (선이 겹치지 않아야하므로 정렬되어야 함)

고등학교에서 배운 조합 표현으로 mCn으로 나타낼 수 있다.

mCn = m-1Cn + m-1Cn-1 

팩토리얼로 풀 수 있지만 위와같은 공식이 있었으므로 dp로 풀어낼 수 있다