코드업 2652

이번 글은 코드업 2652 문제를 풀어보겠습니다.

극장에 n개의 빈 좌석이 있다.
 
k명의 관객들이 영화를 보기 위해서 왔다.

이 관객들이 n개의 좌석에 앉을 수 있는 서로 다른 방법의 수를 구하는 프로그램을 작성하시오. 

(단, k명의 사람을 서로 구분하지 않는다.)

입력
첫 번째 줄에 n 과 k 가 공백으로 구분되어 입력된다.
 
[입력값의 정의역]
1 ≤ k ≤ n ≤ 20

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

 

1. 문제분석

이 문제는 n개의 원소에서 r개를 고르는 방법인 조합과 같습니다.

즉, nCr 을 구하는 것과 같다는 것입니다.

점화식을 생각해보았는데 이항계수와 파스칼의 삼각형을 이용한

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

을 사용해보도록 하겠습니다.

 

+ 파스칼의 삼각형

이항계수와 파스칼의 삼각형

 

2. 순서도

 

3. 코딩

#include <stdio.h>

int f(int a, int b){
  if(b==0 || a==b) return 1;
  return f(a-1, b-1)+f(a-1, b);
}

int main(){
  int n, r;
  scanf("%d %d", &n, &r);
  printf("%d", f(n,r));
  return 0;
}

재귀함수를 이용해 이렇게 짜보았습니다.

 

좌석 수(n), 사람 수(r)로 선언하고 각각 함수 f에서 매개변수 a, b로 하였습니다.

 

사람 수(r)이 0명이거나 좌석 수(n)==사람 수(r) 이면 경우의 수가 1이고

그렇지 않으면 점화식에 대입하여 그 값을 반환해 출력합니다.

 

저는 이렇게 조합과 그 점화식을 이용해서 문제를 풀어보았습니다.

그럼 다음 글에서 보겠습니다.