백준 1010번 : 다리 놓기 (Python)

문제 : www.acmicpc.net/problem/1010

1010번: 다리 놓기

 

풀이

m개의 사이트 중 순서없이 n개를 뽑는 경우의 수를 계산하면 된다.

예를 들어 m=5, n=2 라고 가정하면 5*4 / 2*1 이다.

이는 5*4 = 5*4*3*2*1 / 3*2*1 이므로 5*4*3*2*1 / ((3*2*1) * (2*1)) 로 표현이 가능하다.

dp에 해당 인덱스까지의 모든 숫자의 곱을 저장해둔다.

그 뒤 dp[m]을 dp[m-n]*dp[n]의 값으로 나눠 출력한다.

 

t = int(input())

dp = [0, 1]
for _ in range(t):
    n, m = map(int, input().split(" "))

    if m-n == 0:
        print("1")
        continue

    if len(dp)-1 < m:
        for i in range(len(dp), m+1):
            dp.append(dp[i-1]*i)

    print(dp[m]//(dp[m-n] * dp[n]))