Combination, n개 중 k개를 고르는 방법의 수

문제)Combination

nCk 는 n개 중 k개를 고르는 방법의 수이다.

nCk를 구하는 일반식은 다음과 같다.

위 식은 n!을 이용하기 때문에 n이 커지면 overflow가 발생하여 정확한 값을 구할 수가 없다.

물론 위 방법 외에도 다양한 점화식으로 구할 수 있다.

nCk를 정확하게 구하는 프로그램을 작성하시오.

<입력>

첫 번째 줄에 n과 k가 공백으로 구분되어 입력된다. (단, 1<=n, k<30)

<출력>

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

<입력 예>

5 1

10 5

<출력 예>

5

252

풀이)Combination(S)

이 문제는 수학의 조합 문제로 주어진 공식으로도 조합의 값을 구할 수 있지만, Factorial을 계산할 때 오버플로가 발생할 수 있다.

관계식을 세워보면, 아래와 같이 세울 수 있다.

먼저, 3개 중 2개를 선택하는 경우는 아래와 같다. (파란색이 선택한 경우)

이 경우, 마지막 세번째 물건만 살펴보면 아래 그림과 같이 고르거나 고르지 않은 경우 두가지로 나눌 수 있다.

마지막 물건을 고른 경우엔 마지막을 제외한 2개 물건 중 1개는 고른 상태가 되어야 한다.

마지막 물건을 고르지 않은 경우엔 앞의 두개는 모두 고른 상태가 되어야 한다.

따라서 관계식은 다음과 같은 관계를 얻을 수 있다.

f(n, k) = 마지막 물건을 고른 경우의 수 + 마지막 물건을 고르지 않은 경우의 수

마지막 물건을 고른 경우의 수 = f(n-1, k-1)

마지막 물건을 고르지 않은 경우의 수 = f(n-1, k)

f(n, k) = f(n-1, k-1) + f(n-1, k)

n개의 물건 중 n개를 고르는 경우는 1가지임이 명백하고,

n개의 물건 중 1개를 고르는 경우는 n가지임이 명백하다.

즉, f(n,1)=n, f(n,n)=1이고, 관계식을 정리하면 아래와 같다.

코드)Combination(S)

#include<iostream>
 
using namespace std;
 
int f(int n, int k)
{
    if (k == n) return 1;
    else if (k == 1) return n;
    else return f(n - 1, k - 1) + f(n - 1, k);
}
 
int main()
{
    int n, k;
    cin >> n >> k;
    cout << f(n, k) << endl;
 
    return 0;
}

위 알고리즘은 factorial을 사용하지 않기 때문에 해가 오버플로가 나지 않는 범위라면 오버플로 없이 계산할 수 있다.

그러나 위 알고리즘은 계산량이 너무 많아, n값이 더 커지면 보다 효율적인 아이디어가 필요.