Python / 1010 다리놓기

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

1010번: 다리 놓기

백준 실버 5 문제 중 다리놓기 문제

수학 / 다이나믹 프로그래밍 / 조합론

 

첫째줄에는 테스트케이스의 개수

두번째줄 부터는 n, m 서쪽, 동쪽의 다리를 지을수 있는 사이트의 개수가 주어진다

 

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

[수학] 순열, 조합 공식 총정리

여기 나오는 조합 식을 이용해서 답을 구한다 

 

조합 서로다른 n개중에 r 개를 선택하는 경우의 수

식 n! / (n - r)! r!

 

식을 이렇게 구현하면 이런 코드가된다

 

n = int(input())


def fac(m):
    hap = 1
    for i in range(1, m+1):
        hap *= i
    return hap


for _ in range(n):
    n, m = map(int, input().split())
    answer = fac(m) // (fac(m-n) * fac(n))
    print(answer)

 

 

n 으로 테스트케이스의 수를 입력받고 팩토리얼을 구할 함수를 만들어준다

다음은 테스트케이스들을 입력받고 결과를 출력할 for 문을 만들고 결과를 출력해준다