[Python] 백준 1010 다리 놓기

문제 바로가기

   문제분석   

# 서쪽에 N개, 동쪽에 M개의 다리가 있고, 다리는 서로 겹칠 수 없고 한개씩만 연결 가능하다.

# N < M 이기 때문에, 최대 연결할수 있는 다리의 수는 N개 이며

# M개의 지역에 N개의 다리를 놓는 경우의 수를 구하게 된다면 mCn(이항계수)를 사용해서 구한다.

 

 

   문제풀이   

t = int(input())    # 테스트 케이스

for _ in range(t):  # 테스트 케이스만큼 반복
    n, m = map(int, input().split())    # 0 < N ≤ M < 30 -> mCn = m! // (m-n)!*n!

    def fac(n): # 팩토리얼 재귀함수
        if n <= 1:
            return 1
        return n * fac(n-1)

    print(fac(m)//(fac(m-n) * fac(n)))

# 입력값으로 테스트 케이스의 개수 T를 받는다.

# 케스트 케이스만큼 반복시켜야 하니까 반복문을 돌리고 N,M을 차례로 입력값으로 받는다.

# 공백을 기준으로 split하고 숫자 계산을 위해 map함수로 모두 정수형으로 바꾼다.

# 이항계수를 구하는 공식을 만들기 위해 팩토리얼을 구현하는 함수를 만들고 재귀적으로 호출한다.

• m! / (n!(m-n)!)