[Python] 백준 1010번 - 다리 놓기

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

1010번: 다리 놓기

 

dp 규칙 찾느라 오래 걸렸다..

 

0번째 행은 j+1랑 같은 수가 된다.

dp를 만들 때 인덱스를 고려해서 맨 앞에 값을 하나씩 더 넣어줬으면 편리했을텐데 귀찮아서 안 했다. 이걸 해줬으면 아마 j+1이 아니라 j랑 같은 수가 될 것이다.

 

i == j인 경우 다리 놓는 방법이 1가지이므로 해당 조건을 추가해주었다.

 

그 후부터는 dp[i][j] = dp[i][j-1] + dp[i-1][j-1] 규칙을 발견하여 이를 적용하였다.

 

해당 케이스의 전체 경우의 수를 출력해야 하므로 dp의 마지막 값인 dp[-1][-1]을 출력하면 된다.

 

import sys
input = sys.stdin.readline

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

    for i in range(n):
        for j in range(i, m):
            if i == 0:
                dp[i][j] = j+1
                continue
            if i == j:
                dp[i][j] = 1
            else:
                dp[i][j] = dp[i][j-1] + dp[i-1][j-1]
                
    print(dp[-1][-1])

 

풀고나면 딱히 풀이할 게 많지 않은데... dp... 😢