[BOJ][Python]1010번 풀이

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

1010번: 다리 놓기

t = int(input())
table = [[0 for _ in range(30)] for _ in range(30)]
for i in range(1,30):
    table[1][i] = i
    table[i][i] = 1
for i in range(2,30):
    for j in range(i+1,30):
        table[i][j] = table[i][j-1]+table[i-1][j-1]
for _ in range(t):
    n,m = map(int, input().split())
    print(table[n][m])

혹시 예전에 풀었던 문제가 기억나시나요? 전에는 점화식을 세우기 전에 바로 푸는 법이 떠올랐다면서 리스트를 2개 만들어서 풀었던 문제와 동일한 문제입니다. 이번에는 시간 제한이 0.5초로 타이트해서 점화식을 세워야 했기 때문에 2차원 리스트를 만들어서 해결했습니다. 처음엔 중복 없이 라는 말에 홀려서 순열을 이용해서 풀어보려고 했는데 식이 잘 안세워져서 포기하고 최대한 간단하게 구성해봤습니다.

 

https://justduke.tistory.com/136?category=1226365 

[BOJ][Python]4482번 풀이

이 링크는 위에서 말했던 리스트를 2개 만들어서 풀었다는 문제입니다. 해당 문제도 이 방법과 동일하게 구현 가능하겠네요.