[백준] 1010번 문제 (다리 놓기) 파이썬(Python) 풀이

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

1010번: 다리 놓기

dp = [[1] * 31 for _ in range(31)]
for i in range(31):
    dp[1][i] = i
for i in range(2, 31):
    for j in range(i + 1, 31):
        dp[i][j] = dp[i][j - 1] + dp[i - 1][j - 1]

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

문제에서 입력으로 주어지는 n과 m에 대해 경우의 수를 나타내보면 아래와 같다.

 

/	1	2	3	4	5	6
1	1	2	3	4	5	6
2	X	1	3	6	10	15
3	X	X	1	4	10	20

행이 n, 열이 m을 나타낸다.

1번째 행은 당연하게도 m과 같은 숫자가 된다.

2번째 행부터는 규칙을 발견할 수 있는데 바로,

num[n][m] = num[n][m - 1] + num[n - 1][m - 1]  이와 같은 규칙이 발견된다.

 

따라서 입력이 최대 30까지 주어진다 했으니 배열을 31까지 미리 할당하여 해당 규칙을 토대로 배열을 만들고 입력받은 n과 m에 대하여 dp[n][m] 을 출력하면 된다.