1010 다리놓기 _python

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

1010번: 다리 놓기

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

문제 접근

dp문제.

문제를 읽어보면 M개중 N개를 뽑아라 라는 말로 간추릴수 있다.

조합 공식에 대입만 해주면 되는데, 팩토리얼을 사용하고 범위는 30까지니 dp로 미리 값을 저장해두면 된다.

 

조합 공식이 기억안난다면

https://coding-factory.tistory.com/606

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

코드

from collections import deque
import sys
input = sys.stdin.readline

"""
1010
M개중 N개를 골라라 - 조합. mCn = m!/((m-n)!*n!)
"""

#입력
T = int(input())
dp = [i for i in range(31)]
dp[0]=1

#팩토리얼
def factorial():
    for i in range(3,31):
        dp[i] *= dp[i-1]
factorial()

#연산후 출력
for i in range(T):
    N,M = map(int,input().split())
    print(dp[M]//(dp[M-N]*dp[N]))