(백준 알고리즘 문제풀이) 1010번 다리 놓기

문제

문제 링크

 

문제 접근

• N에서 M으로 가는 경우의 수를 구하는 것이다.
• N이 M보다 작거나 같으므로 조합공식 mCn을 적용시킨다.

조합 공식 (combination formula)

코드

import sys


def factorial(N):
    result = 1
    for i in range(1, N+1):
        result *= i
    return result


T = int(sys.stdin.readline())
for _ in range(T):
    N, M = map(int, sys.stdin.readline().split())
    # M >= N
    # Combination
    ans = int(factorial(M) / (factorial(N) * factorial(M-N)))
    print(ans)

느낀점

조합에 대한 공식을 도출하는데까지의 시간이 좀 걸린 것 같다.