Combination 개수 구하기 (Pascal's Triangle)

Combination(조합) 개수 구하는 방법은?

만약에 nCr을 구하는 프로그램을 c로 구현한다고 하면..
나는 당근 이렇게 짤것이다.. -_-

  1 long long get_combi(int n, int r)
  2 {
  3     int i, j;
  4     long long res;
  5     r = min(r, n-r);
  6     res = 1;
  7     for (i = 1, j = n; i <= r; i++, j--) {
  8         res *= j;
  9         res /= i;
 10     }
 11     return res;
 12 }

위와같이 짜다보면 직관적이긴 한데..
n이 조금만 커지면 중간에 overflow 나고 막장이 된다.. ㅠ_ㅠ

그런데 조합 개수를 파스칼의 삼각형을 이용하여 구할 수 있다


Binomial Theorem (이항정리)에 의해
(x+y)^n 을 전개했을 때 (x^p)*(y^q) 항의 계수는 놀랍게도 nCp 가 된다..
(여기서 당근 p + q = n 이다)

(x+y)^n 을 전개 해보자..

n = 0: 1
n = 1: x^1 + y^1
n = 2: x^2 + 2*x^1*y^1 + y^2
n = 3: x^3 + 3*x^2*y^1 + 3*x^1*y^2 + y^3
n = 4: x^4 + 4*x^3*y^1 + 6*x^2*y^2 + 4*x^1*y^3 * y^4
...
...


여기서 계수들만 쭉 뽑아서 나열해보면 규칙이 있다..

1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
...
...

이게 바로 파스칼의 삼각형인데..
현재 원소의 값은 바로 위에줄에 있는 두개의 원소의 합과 같다..

이러한 규칙을 이용하여 DP로 쉽게 구현할 수 있다.. ㅎㅎ
 

  1 /* Combination (Pascal's Triangle) */
  2
  3 #include <stdio.h>
  4 #include <string.h>
  5 #define MAXN 51
  6
  7 /* combi[n][r] = n C r */
  8 long long combi[MAXN][MAXN];
  9 void get_combi()
 10 {
 11     int i, j;
 12     for (i = 0; i < MAXN; i++) {
 13         combi[i][i] = 1;
 14         combi[i][0] = 1;
 15     }
 16     for (i = 0; i < MAXN; i++) {
 17         for (j = 1; j < i; j++) {
 18             combi[i][j] = combi[i-1][j-1] + combi[i-1][j];
 19         }
 20     }
 21 }