백준 1010번 다리놓기(python3)

다리를 그림으로 그리고 규칙성을 파악하면 

쉽게 풀 수 있는 문제이다.

첫번째 n의 다리와 첫번째 m의 다리를 이어놓고 그 아래의 다리를 보면, 이전에 적용된 다리의 경우의 수가 계속 적용되어 나옴을 확인할 수 있다.

 

n이 1일 경우 m과 같아서 for문 이용해서 미리 만들어주고 그 아래에 위의 공통된 로직을 짜면 된다. 

 

전형적인 dp문제이지만

다른 사람들 풀이를 보니 조합을 이용해서도 많이 푼 것 같다.

 

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


array = [[0] * 30 for _ in range(30)]

for i in range(1, 30):
    array[1][i] = i

for i in range(2, 30):
    for j in range(i, 30):
        for k in range(i - 1, j):
            array[i][j] += array[i - 1][k]

t = int(input())

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