백준_1010_다리 놓기(조합론)

dp = [[0]*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
        elif i < j:
          dp[i][j] = dp[i-1][j-1] + dp[i][j-1]

T = int(input())

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

처음에 직접 풀어봤을 때 factorial 관련해서 규칙이 있는 것을 파악해서 factorial을 사용해서 나눠보기도 하고 더해 보기도하고 지지고 볶았지만 해결하지 못했다. 인터넷에서 확인해 보니 조합 공식을 사용하면 풀 수 있는 문제였다.

확인해보니 DP로도 풀 수 있는 문제여서 DP로 풀기로 했다.

	1	2	3	4	5
1	1	2	3	4	5
2		1	3	6	10
3			1	4	10
4				1	5

1행의 경우 당연히 열의 idx 값이고, 행과 열의 idx가 같으면 1이다.
이 두가지 가 아닌 경우 이전 열의 현재 행과 이전 행을 더한 값으로 채워지는 것을 볼 수 있다.
식으로 표현하면 dp[i][j] = dp[i-1][j-1] + dp[i][j-1] 이렇게 된다.

---

인터넷을 참고하긴 했지만 dp로 풀 수 있다는 것을 알게 된 후 에는 스스로 해결했다.