백준(Python) 1010번 다리 놓기 풀이

Python으로 구현한 1010번 다리 놓기 문제 풀이입니다.

 

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

1010번: 다리 놓기

---

tc = int(input())

def factorial(x) :
  count = 1
  for i in range(2, x + 1) :
    count *= i
  
  return count

for _ in range(tc) :
  a, b = map(int, input().split())
  result = factorial(b) // (factorial(a) * factorial(b-a))
  print(result)

 

문제에서 제시한 두 수의 범위는 m이 n보다 크기 때문에 최대 연결할 수 있는 다리의 개수는 n이다.

 

위 코드에서는 n을 a로 작성하고 m을 b로 작성하였다. 

 

b개의 지역에 a개의 다리를 놓을 수 있는 경우의 수는 bCa 즉, b! / a!(b-a)! 의 연산으로 문제를 해결할 수 있다.

 

factorial( ) 메서드를 생성하여 2부터 전달받은 값까지 곱한 수를 반환하여 최종적으로 b! / a!(b-a)! 한 값을 출력한다.