[백준/Python] 1010번: 다리 놓기

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

1010번: 다리 놓기

조합 라이브러리를 사용하여 풀었더니 시간초과가 발생.

from itertools import combinations

t = int(input())

for _ in range(t):
    # bCa 로 조합을 사용한다. b개에서 a개를 뽑는다
    a, b = map(int, input().split())
    arr = []
    for i in range(1, b + 1):
        arr.append(i)

    print(len(list(combinations(arr, a))))

 

아래와 같은 풀이를 통해 시간초과해결 

조합을 직접 구현하였음.

t = int(input())

for _ in range(t):
    # bCa 로 조합을 사용한다. b개에서 a개를 뽑는다
    x = 1
    y = 1
    a, b = map(int, input().split())
    if a == 1 or b - a == 1:
        print(b)
    else:
        for i in range(a):
            x *= b
            b -= 1
        for j in range(a, 1, -1):
            y *= j
        print(round(x / y))