[백준] 1010. 다리 놓기 (Python)

백준 문제 풀이 - 다이나믹 프로그래밍

📰 문제

---

문제 확인 🏃

💡 입출력 예제

---

3
2 2
1 5
13 29

>> 1
5
67863915

💬 풀이

---

🎵 첫번째 풀이 - DP

T = int(input())        # 테스트케이스

def solution(N, M):

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

    if N == 1:
        return M

    for i in range(1, N+1):
        for j in range(1, M+1):
            if i == 1:
                table[i][j] = j
            else:
                table[i][j] = table[i-1][j-1] + table[i][j-1]

    return table[N][M]

for _ in range(T):
    N, M = map(int, input().split())
    print(solution(N, M))

🎵 두번째 풀이 - 조합

N개 만큼 M에서 선택

import math

T = int(input())        # 테스트케이스

for _ in range(T):
    N, M = map(int, input().split())
    print(math.comb(M, N))

✒️ 생각

---

math에서 comb를 사용하기 위해서는 파이썬의 버전이 3.8 이상이어야 함 (이때, 추가된 기능이기 때문)

다이나믹 프로그래밍으로 풀었을 경우,