[Python]수학3 백준 11050

   문제

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

이항계수가 먼지 생각이 안난다.

찾아보았다.

조합론에서, 이항 계수(二項係數, 영어: binomial coefficient)는 이항식을 이항 정리로 

전개했을 때 각 항의 계수이며, 주어진 크기의 (순서 없는) 조합의 가짓수이다.

nCk라고 생각하면 된다.

nCk=n!/(n-k)!k!이다 물론 n은 k보다 크거나 같다.

https://shoark7.github.io/programming/algorithm/3-ways-to-get-binomial-coefficients

위사이트를 참고하였다.

위 식을보면 팩토리얼의 계산이 3개나 들어가있다.

재귀로 구현한다면 속도면에서 많이 느릴것이다.

동적계획법 활용해 앞서 구했던 값들을 다시 구하지 않도록 구현해야겠다.

n까지의 팩토리얼을 구하고 구한값을 이용하여 이항계수를 구해보겠다.

n,k=map(int,input().split())
 
factorial=[1 for _ in range(n+1)]
 
for i in range(1,n+1):
    factorial[i]=i*factorial[i-1]
 
 
print(factorial[n]//factorial[n-k]//factorial[k])