[백준] python 1010 다리 놓기

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

1010번: 다리 놓기

풀이법

다이나믹 프로그래밍

1.  30 * 30 배열을 만든다

2. 아래의 그림과 같이 생각한다.

배열 표

코드

import sys
input = sys.stdin.readline

t = int(input())

dp = [[0 for _ in range(30)]for _ in range(30)]
for i in range(1, 30):
    for j in range(1, 30):
        if i == 1:
            dp[i][j] = j
        elif i == j:
            dp[i][j] = 1
        else:
            if j > i:
                dp[i][j] = dp[i-1][j-1]+dp[i][j-1]

for _ in range(0, t):
    n, m = map(int, input().split(' '))
    print(dp[n][m])