[Algorithm] combinationpascal

문제

---

n명의 사람중 m명을 순서에 상관없이 뽑는 경우의 수를 조합이라고 하며 nCm으로 나타낸다.

이 조합은 파스칼의 삼각형과 아주 밀접한 관련이 있다고 한다.

n과 m이 주어졌을때 nCm의 값을 출력하는 프로그램을 작성하시오.  

입력

---

첫째 줄에 정수 n, m(0≤m≤n≤30)이 들어온다.

 

출력

---

첫째 줄에 nCm의 값을 출력한다.

 

예제 입력

5 2

예제 출력

10

이 문제를 

#include <stdio.h>

int n,m;

int multiply = 1;

int multiply2 = 1;

int multiply3 = 1;

int main() {

  //Please Enter Your Code Here

  scanf("%d %d",&n,&m);

  

  for(int i=n; i>0; i--){

    multiply = multiply * i;

  }

  for(int i=m; i>0; i--){

    multiply2 = multiply2 * i;

  }

  for(int i=(n-m); i>0; i--){

    multiply3 = multiply3 * i;

  }

  

  printf("%d",multiply/(multiply2*multiply3));

  return 0;

}

다음과 같이 구현했으나, 시간 초과가 떴다.

그러므로 파스칼 삼각형을 공부해보자.

이항계수의 성질을 알아야만 해결할 수 있어서 파스칼 삼각형의 원리를 공부하였다.

<원리>

nCr + nCr+1 = n+1Cr+1 이다.

예를 들어, 10개 중 2개를 고르는 경우의 수는 45개이다. -> 10 x 9 / 2 x 1;

9C1 + 9C2 = 45이다. 

다른 예를 보면, 9개 중 3개를 고르는 경우의 수는 9C3 인데, 

8C2 + 8C3 으로 표현된다. 

<코드>

#include<stdio.h>

int n,m;

int combi[32][32];

int getCombi(int arr[][32], int l, int k)

{

  if(k==1){

    // nC1은 항상 n

    arr[l][k] = l;

    return l;

  }

  if(k==0){

    // nC0 은 항상 1

    arr[l][k] = 1;

    return 1;

  }

  if(l==k){

    // nCn 은 항상 1

    arr[l][k] = 1;

    return 1;

  }

  if(arr[l][k]!=0){

    return arr[l][k];

  }

  

  arr[l][k] = getCombi(arr,l-1,k)+getCombi(arr,l-1,k-1);

  return arr[l][k];

}

int main(){

  scanf("%d %d",&n,&m);

  printf("%d",getCombi(combi,n,m));

  return 0;

}

조합의 문제에서 팩토리얼을 사용하여 재귀 호출로 문제를 풀 경우에는 계산량이 많아져 시간 초과가 발생하는 것을 알 수 있었다.

그러므로 파스칼의 원리와 조합 + (재귀의 흐름) 을 이해하면 조합 문제의 경우 더욱 효율적인 코딩이 가능하다.