[PS] 백준#1010 다리 놓기 / 파이썬

알고리즘 문제 풀이

• 문제 : 다리 놓기
• 해결 : solved
• 분류 : 조합, DP

풀이 방법(1) - 조합

1. 조합 공식을 사용한다
2. n!이 사용되는데 여기서 DP로 n까지의 n! 각 값들을 배열을 이용해 구해놓는다.
3. dp로 만들어 놓은 배열을 이용하여 공식에 따라 계산한다.

풀이 방법(2) - DP

1. n까지의 배열을 초기화하고 각 인덱스는 x개의 동쪽 사이트가 있을 경우로 정의한다.
2. dp[i] 는 i번째 사이트를 포함하는 경우의 수 + 포함하지 않는 경우의 수

   f(n, k) = f(n-1, k) + f(n-1, k-1)

3. dp 배열의 마지막 원소를 출력한다.

소스코드

T = int(input())
for _ in range(T):
    N, M = map(int, input().split())
    dp = [[1] * (M+1) for _ in range(N+1)]

    for i in range(1, N+1):
        for j in range(1, M+1):
            if i > j :
                dp[i][j] = 0
            elif i == j :
                dp[i][j] = 1
            else:
                dp[i][j] = dp[i][j-1] + dp[i-1][j-1]
    print(dp[-1][-1])