문제
nCk는 n개 중에서 k개를 고르는 방법의 수이다.
nCk를 구하는 일반식은 다음과 같다.
(_k^n) = {{n(n-1)...(n-k+1)}\over{k(k-1)...1}} = {{n!}\over{k!(n-k)!}}
위 식은 n!을 이용하기 때문에 n이 커지면 overflow가 발생하여 정확한 값을 구할 수 없다.
물론 위 방법 이외에도 다양한 점화식으로도 구할 수 있다.
nCk를 정확하게 구하는 프로그램을 작성하시오.
입력
첫 번째 줄에 n과 k가 공백으로 구분되어 입력된다.
( 단, 1 ≤ k ≤ n ≤ 30)
출력
구한 답을 첫 번째 줄에 출력한다.
예제 #1
5 1
5
예제 #2
10 5
252
태그
출처
문제해결을 위한 창의적 알고리즘 (고급)| comkiwer
로그인해야 코드를 작성할 수 있어요.