백준 1010번 Python / Math

문제 링크

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

1010번: 다리 놓기

 

풀이

시간 초과 풀이

import itertools

t = int(input())

for _ in range(t):
    n, m = map(int, input().split())
    print(len(list(itertools.combinations(range(m),n))))

 

정답 풀이

import math

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

 

문제를 보고 조합(combination)문제라는 생각이 들었습니다.

그래서 itertools에 combinations() 함수를 이용하면 조합을 구할 수 있기에 리스트에 m만큼의 range를 설정하고 조합을 구해 길이를 출력하는 방식으로 해결하려 했었습니다.

하지만, 저 방법으로 하면 일일이 리스트를 만들어 길이를 출력하는 것이다 보니 예제의 13 29와 같은 수가 들어갈 경우 조합할 수 있는 수가 너무 많아 시간 초과가 발생했습니다.

 

그래서 math 라이브러리로 팩토리얼의 값을 바로 구하고 공식에 직접 대입해 출력하는 방법으로 정답을 맞췄습니다.

$$ C(m,n) = \dfrac{m!}{\left(m-n\right)!n!} $$