[C/C++] 프로젝트 오일러 #115 Counting Block Combinations II

프로젝트 오일러 #115번 문제는 최소 길이가 M 이상인 연속된 빨간색 블록과 검은색 칸(구분자)을 사용하여, 일렬로 배치할 수 있는 경우의 수를 조사하는 문제입니다. 다음과 같은 조건을 갖습니다.

 

1. 줄의 길이(n): 특정 길이 n의 직선 위에 빨간색(R) 칸과 검은색(B) 칸을 배치합니다.

 

2. 빨간색 블록의 최소 길이(M): 하나 이상의 연속된 빨간 칸을 하나의 “빨간색 블록”이라 할 때, 이 블록 하나는 최소한 M개의 연속된 빨간 칸으로 이루어져야 합니다.

 

3. 블록 사이의 구분(검은 칸): 두 개 이상의 빨간색 블록 사이에는 최소한 하나 이상의 검은 칸이 있어야 합니다. 즉, 빨간색 블록이 서로 인접한 형태로 놓이는 것은 허용되지 않습니다.

 

4. 모든 가능한 배치의 수 계산: 위의 조건을 만족하는 모든 가능한 칸 배치 경우의 수를 n에 따라 계산합니다.

이 문제에서 궁극적으로 요구하는 것은 “주어진 최소 블록 길이 M에 대하여, 가능한 배치 경우의 수가 1,000,000(백만)을 초과하는 가장 작은 n은 얼마입니까?“를 찾는 것입니다. 즉, 특정 M값을 설정한 뒤 줄의 길이 n을 늘려가며 가능한 배치 경우의 수를 계산할 때, 해당 경우의 수가 처음으로 1,000,000을 넘게 되는 최소의 n값을 구하는 것이 문제의 목표입니다.

 

Counting Block Combinations

 

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

//------------------------------------------------
//    Project Euler #115 - Counting Block Combinations II
//        - by Aubrey Choi
//        - created at 2015-11-04
//------------------------------------------------
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdint.h>
#include <time.h>
#include <math.h>
#include "isprime.h"

#define    LIMIT    1000000

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;
}

uint64_t CountingBlock(int m, int total)
{
    uint64_t count = 1;

    for( int k = 1 ; ; k++ )
    {
        int n = 2*k+1;
        int r = total-(m+1)*k+1;
        if( r < 0 ) break;
        count += comb(n+r-1, r);
    }

    return count;
}

void solve1()
{
    for( int n = 100 ; ; n++ )
    {
        uint64_t count = CountingBlock(50, n);
        if( count > LIMIT )
        {
            printf("Ans = %d (%ju)\n", n, count);
            break;
        }
    }
}

int main()
{
    clock_t t;

    t = clock();

    solve1();

    printf("Elapsed time is %.3f seconds \n", (float)(clock() - t) / CLOCKS_PER_SEC);
}

 

아래는 주어진 소스 코드를 기능적인 부분 단위로 나누어 말로 풀어서 설명한 내용입니다.

1. comb 함수

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;
}

이 함수는 조합 \(  C(n, r) = \frac{n!}{r!(n-r)!} \)을 계산합니다. 주어진 n과 r에 대해, 조합의 대칭성 \(  C(n, r) = C(n, n-r) \) 을 이용하여 연산량을 줄이고, 반복문을 통해 분자와 분모를 하나씩 계산합니다. 결과는 64비트 정수로 반환됩니다.

2. CountingBlock 함수

uint64_t CountingBlock(int m, int total)
{
    uint64_t count = 1;

    for( int k = 1 ; ; k++ )
    {
        int n = 2*k+1;
        int r = total-(m+1)*k+1;
        if( r < 0 ) break;
        count += comb(n+r-1, r);
    }

    return count;
}

이 함수는 최소 길이 m 이상인 빨간색 블록을 포함하여 길이가 total 인 줄을 배치할 수 있는 모든 가능한 경우의 수를 계산합니다. 초기값으로 count를 1로 설정하는데, 이는 빨간 블록이 없는 경우를 포함하기 위함입니다.

반복문에서 k는 빨간 블록의 개수를 나타내며, k를 1부터 증가시키면서 가능한 배치를 계산합니다. 각 k에 대해 n = 2k+1은 필요한 전체 칸의 수,  r = total - (m+1)k + 1 은 블록 외에 배치해야 할 검은 칸의 수를 의미합니다.  r이 음수가 되면 더 이상 유효한 배치가 없으므로 반복문을 종료합니다. 각 k에 대해 가능한 배치의 수를 comb 함수로 계산하여 count에 누적합니다. 최종적으로 가능한 모든 배치의 수를 반환합니다.

3. solve1 함수

void solve1()
{
    for( int n = 100 ; ; n++ )
    {
        uint64_t count = CountingBlock(50, n);
        if( count > LIMIT )
        {
            printf("Ans = %d (%ju)\n", n, count);
            break;
        }
    }
}

이 함수는 최소 블록 길이가 50일 때, 가능한 배치의 경우의 수가 1,000,000을 초과하는 가장 작은 n 값을 찾습니다. 초기값으로 n = 100을 설정하고, 반복문을 통해 n을 하나씩 증가시키며 CountingBlock 함수를 호출하여 경우의 수를 계산합니다. 만약 count가 LIMIT인 1,000,000을 초과하면 해당 n 값을 출력하고 루프를 종료합니다.

4. main 함수

int main()
{
    clock_t t;

    t = clock();

    solve1();

    printf("Elapsed time is %.3f seconds \n", (float)(clock() - t) / CLOCKS_PER_SEC);
}

main 함수는 프로그램의 진입점으로, 전체 실행 흐름을 제어합니다. 실행 시간을 측정하기 위해 프로그램 시작 시 clock을 호출하고, solve1 함수를 호출하여 문제를 해결합니다. 결과값을 출력한 후, 실행 시간을 계산하여 프로그램 실행 시간을 출력합니다.

5. 매크로 정의

#define    LIMIT    1000000

매크로는 상수 LIMIT를 정의하여, 가능한 배치 경우의 수가 초과해야 하는 기준 값을 설정합니다. LIMIT은 코드에서 반복적으로 사용되므로 매크로를 통해 코드의 가독성과 유지 보수성을 높입니다.