python 백준1010 다리 놓기(BOJ1010)

문제링크 : https://www.acmicpc.net/problem/1010

1010번: 다리 놓기

이문제는 조합 공식을 사용하면 바로 풀수있다

이런 문제들은 식만 뽑아낸다면 참 쉬운데 문제는 점화식을 못뽑아내면 손도 못대겠다는것..

쨌든 이 문제는 처음에 math라이브러리를 써서 풀었었는데

그랬더니 메모리를 좀 잡아먹는것같아서 팩토리얼을 따로 정의해서 풀었다

import sys

input = sys.stdin.readline

#팩토리얼
def factorial(num):
  result = 1
  for i in range(num, 0, -1):
    result *= i
  return result

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

#입력과 동시에 조합공식 사용
for i in range(t):
  n,m = map(int, input().split())
  #분모
  denominator = factorial(m-n) * factorial(n)
  #분자
  numerator = factorial(m)
  #출력
  print(numerator//denominator)

아래는 팩토리얼을 직접 정의했을때와 math라이브러리의 메모리,시간 차이