[파이썬 / 백준 1006번] 다리놓기

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

 

처음에는 조합을 구해서 카운트 하려다가 예제의 마지막 케이스를 보고 안될 것 같다고 생각을 했다.

오랜만에 조합의 개수를 구하는 식을 떠올리려고 하니,, 전혀 기억 안남..

 

조합의 개수 구하는 식 (nCr)

: n(n-1)(n-2). . . .(n-r+1) / r!

 

어쨌든 조합 개수를 구하는 식을 구해서 처음에 제출했는데 맞았다.

다른 분 하시는 것을 보니까 !(팩토리얼) 값 구할 때 동적계획법을 이용 하셔서 활요해서 풀이했다.

 

T=int(input())
for _ in range(T):
    W,E=map(int,input().split())
    dp=[1 for _ in range(E+1)]
    for i in range(1,E+1):
        dp[i]=i*dp[i-1]
    print((dp[E]//dp[E-W])//dp[W])

미리 dp 리스트를 만들어 놓고 하려니까 수행시간이 더 늦어진다..

왜지?,,

이유는 모르겠음