본문 바로가기
Programming/Project Euler

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

by 작은별하나 2016. 6. 9.
반응형

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

 

 

n이 1부터 100까지 변할 때, 조합 숫자 

을 계산할 때, 1백만이 넘는 결과가 나오는 갯수를 적으면 됩니다.

 

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

 

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

 

단, 조합을 계산하는 곱하기 횟수가 증가하니, 실제 곱하기 횟수로 따진다면, 

정도의 복잡도를 가집니다.  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;
}

 

댓글