[Baekjoon][1010] 실버5 다리 놓기 - Python

🌉 다리 놓기

---

💡 문제 이해하기 및 풀이 아이디어

서쪽과 동쪽을 이으는 서로 겹치지 않는 다리의 경우의 수를 구해야 한다

 

 

 

✅ 풀이 코드

# 다리 놓기
T = int(input())

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 # N이 1일 때

    # N이 2 이상일 때
    for i in range(2, n+1):
        for j in range(i, m+1):
            for k in range(j, i-1, -1):
                dp[i][j] += dp[i-1][k-1]
    return dp[n][m]

for _ in range(T):
    N, M = map(int, input().split())
    print(bridge(N,M))