[백준, 1010번] 다리 놓기

역시 수학 공식을 좀 알고 있어야 편하게 알고리즘을 풀 수 있다는 것을 조금 느꼈다...

• 처음 접한 방법으로는 당연히 조합으로 생각해서 combinations로 구한 다음 길이를 조회해야겠다라고 했지만
• 시간을 보니 0.5초이기도 하고 해당 방법은 너무 오래 걸릴 것이라는 것을 인지해서
• 다른 방법이 있을까 하고 짱구를 굴렸지만... 쉽지 않았고 조합 공식을 찾아보니 첫 번째 코드를 구현할 수 있었다.
• 우선 nCm 조합의 경우
  • n! / (n-m)! * m! 이 되고 
  • 현재 다리 놓기 문제에서는 m이 더 크고 n으로 된 조합의 개수를 찾기에
  • mCn의 경우가 되어 아래처럼 구현하게 되었음.

# 공식을 활용한 풀이
import sys
from math import factorial
input = sys.stdin.readline
for _ in range(int(input())):
    n,m = map(int,input().split())
    print(int(factorial(m)/(factorial(m-n)*factorial(n))))

 

# 시간 초과 코드
import sys
from itertools import combinations
input = sys.stdin.readline
for i in range(int(input())):
    n,m = map(int,input().split())
    print(len(list(combinations([i for i in range(m)],n))))