[C/C++] 프로젝트 오일러 #114 Counting Block Combinations I (조합)

프로젝트 오일러 114번 문제는 길이가 n인 일렬의 칸에 일정한 조건을 만족하도록 빨간 블록을 배치하는 방법의 수를 세는 것에 관한 문제입니다. 이 때 사용되는 빨간 블록은 최소 3칸 이상의 길이를 가져야 하며, 빨간 블록들 사이에는 적어도 하나 이상의 검은 칸이 존재해야 합니다. 또한, 빨간 블록을 전혀 놓지 않는 경우도 하나의 가능한 배치로 포함합니다.

문제에서 정의하는 함수 f(n)은 길이가 n인 칸에 위와 같은 규칙을 적용했을 때 나올 수 있는 모든 가능한 배치의 수를 나타냅니다. 주어진 예시로, n=7일 때 f(7)의 값이 특정 수(17)로 제시되며, f(50)의 값도 매우 큰 수(16475640049)로 주어집니다. 문제는 이러한 함수 f(n)의 값을 확장해 나갈 때, f(n)이 1,000,000을 초과하는 n의 개수가 얼마인지 묻습니다.

즉, 이 문제에서는 일정한 규칙(빨간 블록의 배치 조건) 아래에서 칸의 길이를 변화시킬 때 가능해지는 배치의 가짓수가 어떻게 증가하는지를 살펴보고, 그 증가 속도를 기준으로 f(n)이 특정 기준값(1,000,000)을 넘어서는 지점을 파악하는 것을 요구하고 있습니다.

 

counting block combination

 

제가 문제를 풀기 위해서 작성한 소스입니다.

//------------------------------------------------
//    Project Euler #114 - Counting Block Combinations I
//        - by Aubrey Choi
//        - created at 2015-04-02
//------------------------------------------------
#include <stdio.h>
#include <stdint.h>

uint64_t comb(int n, int r);

int main()
{
    uint64_t count = 1;

    for( int k = 1 ; ; k++ )
    {
        int n = 2*k+1;
        int r = 50-4*k+1;
        if( r < 0 ) break;
        count += comb(n+r-1, r);
    }
    printf("ans = %ju\n", count);
}

uint64_t comb(int n, int r)
{
    uint64_t c = 1;
    if( 2*r > n ) r = n-r;
    for( int i = 1 ; i <= r ; i++ )
    {
        c *= n--;
        c /= i;
    }
    return c;
}

 

이 코드는 특정한 수열을 이용해 가능한 배치의 총 개수를 계산하는 형태를 취하고 있습니다. 전체적으로 다음과 같은 기능들이 존재합니다.

 

1. 메인 로직(main 함수):
• count 변수를 1로 초기화한 뒤, k 값을 1부터 시작하여 반복문을 수행합니다.
• 각 반복에서 n과 r 값을 특정 규칙( n = 2*k+1, r = 50-4*k+1 )으로 계산합니다.
• r 값이 음수가 되는 순간 반복문을 종료합니다.
• 반복 과정에서 comb(n+r-1, r)로 계산된 조합 값을 count에 더해 누적합니다.
• 결국 반복이 끝나면 count에 문제에서 요구하는 최종 결과값이 저장되고, 이를 출력합니다.

 

2. 조합 함수(comb 함수):
• comb(int n, int r)는 수학적인 조합(이항계수) C(n, r)를 계산하는 함수입니다.
• r이 n-r보다 클 경우 대칭성을 이용해 계산량을 줄입니다(예: C(n, r) = C(n, n-r)).
• 이후 c *= n-- / i 형태로 반복 곱셈과 나눗셈을 통해 C(n, r)을 구합니다.
• 이 함수는 큰 수를 다루기 위해 uint64_t형을 사용하며, 오버플로우에 주의하기 위한 간결한 로직을 갖추고 있습니다.

정리하자면, 이 코드는 프로젝트 오일러 #114 문제의 조건에 따른 배치 가능성의 총 수를 효율적으로 계산하기 위해 특정한 점화식이나 수열을 기반으로 한 반복문과, 이를 뒷받침하는 조합 함수를 이용하는 구조로 되어 있습니다. main 함수에서는 주어진 규칙에 따라 n과 r을 변화시키며 해당 조합 값을 더해나가고, comb 함수는 그러한 조합 연산을 빠르고 정확하게 수행하는 역할을 담당합니다.