[조합] nCr 쉽게 구하기. (수정 20190604)

nCr 쉽게 구하기 (수정 20190604)

 오랫만에 와서 살펴보니 코드와 예시를 든 이미지가 잘못되서 수정하였습니다 ㅜㅡㅜ 

 nCr 같은 경우는 n개의 숫자에서 r개를 뽑는 경우의 수이다. 경우의 수를 구하는 경우에서 많이 사용한다.  nCr의 수식은 아래와 같다.

 즉 매번 이 수식을 사용한다는 것은 n! , r!, (n-r)! 를 사용해야 한다. 즉 여기서 말하고자 하는 것은 이 것을 매번 사용할때마다 구하지 않고 미리 다 구해놓아서 그 숫자를 사용하는 것이다. 

  이것을 1개를 뽑는것 부터 n개를 뽑는 것 까지의 조합을 쭈욱 정리하다 보면 숫자의 특성이 나올 것이다. 

 위의 것에서 보면 1개에서 뽑는 경우의 수에서 6개의 경우수를 뽑는 것을 쭈욱 나열 한 건데 여기서 숫자가 어떻게 나오는 지에 대한 일정 패턴이 눈에 보일 것이다. 그 것은 바로 아래의 식이다. 

 저 식이 나오는 이유는 간단하다. 왜냐하면 n개의 공에서 r개를 뽑는 경우의 수는 어찌보면 n-1개의 공에서 r개를 뽑는 수와 n-1 개의 공에서 이미 하나를 뽑았다고 생각하고 r-1개를 뽑는 수를 더한것과 같기 때문이다. 

 즉 위의 성질을 이용하여서 미리 조합의 수를 구해놔서 그것을 호출하면 된다. 

까지 미리 구하는 코드

그래서 50개에서 r 개를 뽑는 경우의 수까지 미리 만드는 코드로 예를 들겠다. 이 조합의 숫자는 2차원 배열로 만들 수 있다.

int main(void){
 
    // [n][r] 이다.
    unsigned long long Combination[51][51] = {};
    Combination[1][0] = 1;    
    Combination[1][1] = 1;
    for (int i = 2; i <= 50; i++){
        Combination[i][0] = 1;
        for (int j = 1; j <= 50; j++){
            Combination[i][j] = Combination[i - 1][j - 1] + Combination[i - 1][j];
         }
    }
    return 0;
}