백준 1010번 다리놓기 파이썬 (python code)

1010번

실버5

 

www.acmicpc.net/problem/1010

 

1010번: 다리 놓기

조합문제이다.

그냥 C(M,N)로 풀면된다.

 

풀이1(comb 사용)

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

 

풀이2(comb사용 x)

import math
T= int(input())
for i in range(T):
    N,M=map(int,input().split())
    answer=1
    for _ in range(N):
        answer*=M
        M-=1
    print(answer//math.factorial(N))

 

하지만 주의할점은 factorial(M)/ factorial(M-N)factorial(N)

으로 풀면 시간이 오래걸린다.( M의 facotrial을 다 구해야 하기 때문)