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 }

'Problem Solving > Algorithm notes' 카테고리의 다른 글

KMP (Knuth-Morris-Pratt) Algorithm  (0) 2009.11.15
Bell Number  (0) 2009.07.12
Finding Minimum Path Cover in DAG  (0) 2009.06.15
Plane Equation (평면의 방정식)  (0) 2009.04.16
Ellipse (타원)  (0) 2009.04.15
Number of Swap Operations  (0) 2008.07.24
소수 구하는 방법 (Sieve of Eratosthenes)  (2) 2008.07.15
Horner's Rule  (0) 2008.05.04
GCD SUM  (0) 2008.03.18
Erdos & Gallai  (0) 2008.03.04

to Top