[백준 1010] 다리 놓기 with Python

문제 링크

www.acmicpc.net/problem/1010

1010번: 다리 놓기

풀이

import math
t = int(input())
for i in range(t):
    n, m = map(int, input().split())
    print(math.factorial(m) // (math.factorial(m-n) * math.factorial(n)))

다리를 짓는 경우의 수는 다리가 놓일 위치 M개 중에 다리의 개수인 N개를 고르는 경우의 수이므로, mCn과 같다.

mCn = m!/(m-n)!*n! 이므로, math 모듈의 factorial을 이용하여 풀었다.

 

math 모듈을 활용하지 않고 factorial을 직접 구현하여 풀면 다음과 같다.

def factorial(x):
    if x <= 1:
        return 1
    else:
        return factorial(x-1) * x

t = int(input())
for i in range(t):
    n, m = map(int, input().split())
    print(factorial(m) // (factorial(m-n) * factorial(n)))