Informatica Online Judge

  서로 다른 n개 중에서 r개 순서 없이 고르기(재귀)(설명) [1894 / 0766]

Time Limit(Test case) : 1000 (ms)
Number of users who solved : 100   Total Tried : 101


The Champion of this Problem (C++) : gs16109 - 0ms / 95byte
My Best Submission (C++) : N/A

[koistudy.net (T. HS Jeon 2017)]

Background

*주의사항 : 이 문제는 재귀 설계 문제로서 반복문을 사용한 코드는 채점이 되지 않습니다.
------

서로 다른 n개 중에서 r개를 순서 없이 고르는 방법의 가짓수를 출력하시오.
(단, 반복문은 사용할 수 없다.)

예를 들어 1, 2, 3 서로 다른 3개 중에 2개를 고를 수 있는 방법의 가짓수는 (1, 2), (2, 3), (1, 3)의 3가지이다.


참고
p개 중에서 q개를 순서 없이 고르는 방법의 가짓수는
(p-1)개 중에서 (q-1)개를 선택하고 마지막 p번째 것을 선택하는 경우의 가짓수 +
(p-1)개 중에서 q개를 선택하고 마지막 p번째 것을 선택하지 않는 경우의 가짓수 이다.

f(p, q)을 p개 중에서 q개를 순서 없이 선택하는 방법의 가짓수라고 정의하면,
위의 의미를 다음과 같은 점화 관계식으로 표현할 수 있다.

f(p, q) = f(p-1, q-1)+f(p-1, q)

재귀 호출을 중단시키기 위해 가장 작은 경우나 특별한 몇 가지 경우를 생각해보면
- p개 중에서 1개를 순서 없이 선택하는 방법의 가짓수는 p,
- p개 중에서 p개를 순서 없이 선택하는 방법의 가짓수는 1,
- 10개 중에서 20개를 순서 없이 선택하는 방법의 가짓수는 0,
...
와 같은 경우들을 생각해 낼 수 있다.

Input

int 형 정수 n 과 r 이 공백을 두고 입력된다.
(1 <= n,r <= 25)

Output

서로 다른 n개 중에서 순서 없이 r 개를 고를 수 있는 방법의 가짓수를 출력한다.

IO Example

입력
3 2

출력
3

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