[ BOJ 1010 ] 다리 놓기(Python)

문제

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

강 서쪽에 n개의 지점, 강 동쪽에 m개의 지점이 있을 때 n개의 다리를 지으려고 한다. (n <= m)
중요한 것은 이때 다리가 겹치면 안된다는 것이다.

문제 풀이

dp 문제는 그림을 그려야 눈에 확 들어오는 것 같다.

우선 가장 위에 고정선을 그어주고, 그 이외의 다른 점들끼리 이어질 수 있는 경우의 수를 생각해보았다.

• n이 1일때, 경우의 수는 m개이다.
• n이 2 이상일 때, 고정선을 기준으로 이외의 점들을 잇는 경우의 수로 나누어보자.

n = 2, m = 4 인 (2)번의 경우, 가장 위의 점을 고정선으로 두었을 때 n = 1, m = 3 인 (1)번이 보이는 것을 확인할 수 있다. (; 연두색 영역)

따라서 점화식은 다음과 같이 생각할 수 있다.

dp[n][m] = dp[n-1][m-1] + dp[n-1][m-2] + ... + dp[n-1][n-1]

코드

import sys
input = sys.stdin.readline

# 다리는 겹치면 안된다.
def bridge(n,m):
    dp = [[0 for _ in range(m+1)] for _ in range(n+1)]

    for i in range(1,m+1):
        dp[1][i] = i

    for j in range(2,n+1):
        for k in range(j,m+1):
            for l in range(k,j-1,-1):
                dp[j][k] += dp[j-1][l-1]

    return dp[n][m]

T = int(input().rstrip())
for _ in range(T):          
    n, m = map(int,input().rstrip().rsplit())
    print(bridge(n,m))