[백준/1010] 다리 놓기 (with 파이썬)

✔ 문제

---

✔ 풀이

import sys
input = sys.stdin.readline

def factorial(x):
    num = 1
    for i in range(1, x+1):
        num *= i
    return num

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

---

✔ 후기

뭔가 조합보다 dp가 먼저 생각났는데 아무리 생각해도 어떻게 풀어야할지 모르겠어서 처음부터 다시 생각했다.

조합론 문제기 때문에 nCk로도 풀 수 있었는데 왜 dp가 먼저 떠올랐는지...

하여튼 앞에서 푼 이항 계수 문제들처럼 factorial을 사용해서 nCk 공식으로 풀었다.

dp로 푸는 법은 구글링해서 찾아봐야겠다.