[기초-재귀설계] 서로 다른 n개 중에서 r개 순서 없이 고르기(재귀)(설명)(C) - 문제

본 문제는 C 의 빠른 기초 학습을 위해 설계된 문제로서 C 코드 제출을 기준으로 설명되어 있습니다.
------

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

서로 다른 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,
...
와 같은 경우들을 생각해 낼 수 있다.

1294: [기초-재귀설계] 서로 다른 n개 중에서 r개 순서 없이 고르기(재귀)(설명)(C)

문제 설명

입력 설명

출력 설명

입력 예시 Copy

출력 예시 Copy

도움

출처/분류