Informatica Online Judge

  Combination (Tiny) [0185 / 00B9]

Time Limit(Test case) : 2000(ms)
Number of users who solved : 1009   Total Tried : 3700


The Champion of this Problem (C++) : gs17033 - ms / 90byte
My Best Submission (C++) : N/A

[]

Background

nCr은 n개 중에서 r개를 고르는 방법의 수이다.

nCr을 구하기 위해서는 일반적으로 n!을 구한다. 하지만 n이 커지면 overflow가 발생하여

정확한 값을 구할 수 없다.

하지만 다음과 같은 점화식을 세우면 정확한 값을 구할 수 있다.

nCr = n-1Cr-1 + n-1Cr

물론 위 점화식 이외에도 다른 점화식도 구할 수 있으며, 그 이외에도 다른 방법으로 풀 수 있다.

nCr을 정확하게 구하는 프로그램을 작성하시오.

(컴퓨터프로그래밍 수업용 수행평가에서는 backtracking을 이용하여 구해보자.)

Input

첫 번째 줄에 n과 r이 공백으로 구분되어 입력된다. ( 단, 1 <= n, r < 30 )

Output

구한 답을 첫 번째 줄에 출력한다.

IO Example

입력
10 5

출력
252

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]