프로젝트 오일러 #53 : 조합 선택

이번 문제는 간단한 문제입니다. 조합 공식만 알면 쉽게 문제를 풀 수 있습니다.

 

combinations

 

n이 1부터 100까지 변할 때, 조합 숫자 \(_nC_r\)을 계산할 때, 1백만이 넘는 결과가 나오는 갯수를 적으면 됩니다.

단순무식한 방법으로 하더라도, 총 10,100 번 조합 계산을 하면 됩니다.

 

\(_nC_r = _nC_{n-r}\)이라는 사실을 알고 있다면, 그 절반으로 줄테고요. 대칭형인데, 단순증가 단순감소 패턴이라는 것을 아신다면, 더 횟수를 줄일 수 있습니다.

 

단, 조합을 계산하는 곱하기 횟수가 증가하니, 실제 곱하기 횟수로 따진다면, \(O(n^3)\)정도의 시간 복잡도를 가집니다. n이 100정도이니, 시간이 아주 조금 더 걸리는 것 뿐이지, 계산 못 할 정도는 절대 아닙니다.

 

저는, 조금 특이한 방법으로 문제를 풀어봤습니다.

 

바로 파스칼의 삼각형을 이용하는 것인데요.

 

위의 그림에서 보다시피, 삼각형의 왼쪽변과 오른쪽변은 1로 채워져 있습니다. 삼각형 안의 값은 바로 위에 인접한 두개의 값의 합을 이용합니다.

 

저는 이 원리를 이용해서, 배열에 해당 n에 해당하는 값들을 저장해놓고, 그 값을 이용해서 숫자를 찾는 방식을 이용했습니다.

 

예를 들어서 4번째 줄이라고 한다면, 배열에는

1 3

이 들어있습니다.

 

그 다음에는 바로 이전값들하고 저장하면서 숫자를 늘리는 것이죠.

1 4 6

 

제가 작성한 소스는 다음과 같습니다.

#include <stdio.h>
#include <stdint.h>

int GetCombination(int n, int r);

int main()
{
    int combs[20];

    for( int i = 0 ; i <= 10 ; i++ )
    {
        combs[i] = GetCombination(23, i);
        printf("C(%d, %d) = %d\n", 23, i, combs[i]);
    }

    int first = 10;
    int n = 23;
    int count = n+1-first*2;
    for( n++ ; n <= 100 ; n++ )
    {
        for( int i = first-1 ; i > 0 ; i-- )
        {
            combs[i] += combs[i-1];
            if( combs[i] > 1000000 ) first = i;
        }
        count += n+1-first*2;
    }
    printf("ans = %d\n", count);
}

int GetCombination(int n, int r)
{
    int c = 1;
    for( int i = 0 ; i < r ; i++ ) { c *= n-i; c /= i+1; }
    return c;
}

 

이 코드는 조합(Combination)을 계산하고, 특정 조건을 만족하는 경우를 세는 프로그램입니다. 다음은 각 부분에 대한 설명입니다.

1. GetCombination 함수:

이 함수는 두 개의 정수 n과 r을 받아 조합을 계산합니다. 조합 공식은 C(n, r) = n! / (r!(n-r)!)로 정의되며, 여기서 n개의 원소 중 r개의 원소를 선택하는 경우의 수를 나타냅니다.

int GetCombination(int n, int r)
{
    int c = 1;
    for( int i = 0 ; i < r ; i++ ) {
        c *= n - i; // 분자를 계산
        c /= i + 1; // 분모를 계산
    }
    return c;
}

2. main 함수:

주요 로직은 조합을 구한 뒤, 1백만을 넘는 값을 가진 조합을 찾고, 그에 따라 계산을 진행합니다.

2.1 배열 초기화:

먼저 combs 배열을 사용하여 C(23, i) 값을 i = 0부터 10까지 계산하여 배열에 저장합니다.

for (int i = 0; i <= 10; i++)
{
    combs[i] = GetCombination(23, i);
    printf("C(%d, %d) = %d\n", 23, i, combs[i]);
}

2.2 조합 계산 및 조건 적용:

그다음, n 값을 증가시키면서 배열의 조합 값을 업데이트합니다. 이때 각 combs[i] 값이 1백만을 넘는 경우에 first 변수를 조정하고, count 값을 업데이트합니다.

int first = 10;
int n = 23;
int count = n + 1 - first * 2;
for (n++; n <= 100; n++)
{
    for (int i = first - 1; i > 0; i--)
    {
        combs[i] += combs[i - 1];
        if (combs[i] > 1000000)
            first = i;
    }
    count += n + 1 - first * 2;
}

이 부분에서는 C(n, r) 값이 1백만을 초과할 때마다, first 변수를 갱신하며 계산을 진행합니다.

3. 결과 출력:

최종적으로 count 값을 출력하여 프로그램이 종료됩니다.

printf("ans = %d\n", count);

요약:

• 이 프로그램은 C(n, r) 값을 계산하고, 값이 1백만을 초과하는 경우를 찾아 이를 바탕으로 계산을 진행합니다.
• n = 23부터 시작해 n = 100까지 조합을 계산하며, 해당 조건을 만족하는 경우를 센 결과를 출력합니다.