백준 1010 : 다리 놓기

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

1010번: 다리 놓기

 

해결 방법 : DP

 

• 왼쪽 사이트 N은 모두 채워지므로, 오른쪽 사이트 M에 대해 N개를 뽑는 '조합'이 구하고자 하는 값과 같다.
  • (M개중에 선별된 N개의 사이트에 겹치지 않도록 순차적으로 다리를 놓을것이기 때문에 더 이상 고려할 부분 X)
• nCr = nCr-1 + n-1Cr-1 
  
  1. 다리 3개 중에서 2개를 고르는 조합 = 3C2
  2. 마지막 다리 하나를 제외하고 2개를 고르는 조합 = 2C2
  3. 마지막 다리 하나를 포함하고 2개를 고르는 조합 = 2C1

import sys
input = sys.stdin.readline

def solution(NM):
    N = M = 31 # maximum 
    dp = [[1]*M for _ in range(N)]

    for n in range(1, N):
        for m in range(n, M):
            if n == m: # n == m이면 경우의 수는 1
                continue

            dp[n][m] = dp[n][m-1] + dp[n-1][m-1] # mCn = m-1Cn + m-1Cn-1

    answer = ''
    for N, M in NM:
        answer += str(dp[N][M]) + '\n'

    return answer[:-1]

if __name__ == '__main__':
    T = int(input())
    NM = [map(int, input().split()) for _ in range(T)]
    result = solution(NM)
    print(result)