[백준] 1010번 다리놓기

⛏ 문제 파악

• 양 편의 다리 놓기 적절한 장소의 숫자를 제공한 뒤, 다리를 놓을 수 있는 경우의 수를 구하는 문제
• 조합론으로 풀면 간단하다.

👉🏻  답안

from math import factorial

T = int(input())
result = 0

for _ in range(T):
  N, M = map(int, input().split(' '))
  if N == M:
    result = 1
  elif N > M:
    result = factorial(N) // (factorial(N-M) * factorial(M))
  elif M > N:
    result = factorial(M) // (factorial(M-N) * factorial(N))
  print(result)

📑  간단한 설명

• 우선 사랑스러운 파이썬의 math를 임포트하고, 팩토리얼을 쓴다.
• N == M 이 같을 경우는 경우의 수가 1 밖에 없고,
• N > M 인 경우, M > N인 경우를 나눠서 조합론을 이용하여 풀면 된다.
• 만약 팩토리얼을 직접 구현하고 싶은 경우는 아래와 같이 풀면 되겠다. 이게 시간효율이 아주 미세하게 좋다.

T = int(input())
result = 0

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

for _ in range(T):
  N, M = map(int, input().split(' '))
  if N == M:
    result = 1
  elif N > M:
    result = factorial(N) // (factorial(N-M) * factorial(M))
  elif M > N:
    result = factorial(M) // (factorial(M-N) * factorial(N))
  print(result)