[백준] 1010번 : 다리 놓기

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

1010번: 다리 놓기

다이나믹 프로그래밍으로 문제를 해결하였고 점화식은 dp[n][m] = dp[n-1][m-1] + dp[n-1][m] 으로 도출하였다.

 

테스트 케이스 서쪽노드2, 동쪽노드 4

 

dp[2][4] = d[1][3] + dp[1][4]는 서쪽노드의 첫번째노드가 동쪽의 첫번째 노드와 연결되어있는 경우와 연결되지 않는 경우의 수의 합이다.

 

1. 서쪽첫번째 노드가 동쪽 첫번째 노드와 연결되어 있는경우

  - dp[1][3] 이다. 즉, 서쪽노드에는 1개의 노드와 동쪽노드에는 3개의 노드만 남은 상태임으로 3

2. 서쪽첫번째 노드가 동쪽 첫번째 노드와 연결되어 있지 않는경우

 - dp[1][4] 이다. 즉, 서쪽노드는 1개가 남에되고 동쪽 노드는 4개의 노드가 남은 상태임으로 4

dp[2][4] = 7이라는 결과가 도출된다.

T = int(input())
for _ in range(T):
    N, M = list(map(int, input().split()))
    dp = [[0 for _ in range(N+1)] for _ in range(M+1)]
    for i in range(N+1):
        dp[i][i] = i
    
    for i in range(M+1):
        dp[i][1] = i
        
    for i in range(2, M+1):
        for j in range(2,N+1):
            dp[i][j] = dp[i-1][j-1] + dp[i-1][j]
            
    print(dp[M][N])