[BOJ:1010] 다리놓기

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

Note

서쪽과 동쪽의 사이트 마다 1부터 N,M으로 번호를 부여하고 두 사이트 간의 다리 사이의 연결 상태를 직접 그려보다가 트리로 표현하면 편리하겠다 싶어 수형도, 트리로 표현하다보니 규칙을 발견했다. 교차하면 안되기 때문에 현재 연결한 다리의 다음 번호의 다리는 직전 번호의 연결 사이트 보다 최소 1이 큰 값들에만 연결해야 한다. 이 규칙에 따라 트리를 그리다 보면 이전 단계에서 확인한 경우를 다시 구해야하는 경우가 생기게 된다. 그경우 DP배열에 저장해두어 다시 연산하는 과정을 축소했다.

Code

import sys

def recur(west, east):
    global checked, DP, n,m
    if west >=n:
        checked[west][east] = True
        DP[west][east] = 1
        return DP[west][east]
    else:
        for next_east in range(east+1, m+1):
            if not checked[west+1][next_east]:
                DP[west][east] += recur(west+1, next_east)
            else:
                DP[west][east] += DP[west+1][next_east]
        checked[west][east] = True
        return DP[west][east]

input = sys.stdin.readline

T = int(input())
for _ in range(T):
    n, m = map(int,input().split())
    DP = [[0]*(m+1) for _ in range(n+1)]
    checked = [[False]*(m+1) for _ in range(n+1)]
    for east in range(1,m+1-n +1):
        DP[1][east] += recur(1,east)
    print(sum(DP[1]))