[C/C++] 프로젝트 오일러 #43 : 부분 문자열 나누어 떨어지기

Project Euler #43 - Sub-string Divisibility 문제는 특정한 성질을 만족하는 팬디지털(pandigital) 숫자를 찾고, 그들의 합을 구하는 문제입니다.  이번 문제도 간단한 문제입니다. (난이도 5%)

 

문제 설명

 

0부터 9까지의 숫자를 각각 한 번씩만 사용하여 만들 수 있는 10자리 숫자를 0

9 팬디지털 숫자라고 합니다. 예를 들어, 1406357289는 10자리 0~9 팬디지털 숫자입니다.

이 문제에서는 단순히 팬디지털 숫자를 생성하는 것이 아니라, 특정한 부분 문자열(sub-string) 이 특정한 소수(prime number)로 나누어지는지를 검사해야 합니다. 구체적으로, 10자리 팬디지털 숫자에서 아래 조건을 만족하는 숫자를 찾아야 합니다.

 

조건 - 부분 문자열이 특정 소수로 나누어지는 성질

팬디지털 숫자를 d₀d₁d₂d₃d₄d₅d₆d₇d₈d₉라고 할 때, 다음 조건을 만족해야 합니다.
• d₁d₂d₃ (2~4번째 자리 수로 이루어진 세 자리 수) 는 2로 나누어져야 합니다.
• d₂d₃d₄ (3~5번째 자리 수로 이루어진 세 자리 수) 는 3으로 나누어져야 합니다.
• d₃d₄d₅ (4~6번째 자리 수로 이루어진 세 자리 수) 는 5로 나누어져야 합니다.
• d₄d₅d₆ (5~7번째 자리 수로 이루어진 세 자리 수) 는 7로 나누어져야 합니다.
• d₅d₆d₇ (6~8번째 자리 수로 이루어진 세 자리 수) 는 11로 나누어져야 합니다.
• d₆d₇d₈ (7~9번째 자리 수로 이루어진 세 자리 수) 는 13으로 나누어져야 합니다.
• d₇d₈d₉ (8~10번째 자리 수로 이루어진 세 자리 수) 는 17로 나누어져야 합니다.

즉, 각 부분 문자열이 정해진 소수로 나누어 떨어지는 성질을 가져야 합니다.

 

목표

 

위의 조건을 만족하는 10자리 팬디지털 숫자들을 찾아 그 합을 구하는 것이 문제의 목표입니다.

예제 숫자인 1406357289는 다음과 같이 조건을 만족합니다.
• 406 ÷ 2 = 203 (✔)
• 063 ÷ 3 = 21 (✔)
• 635 ÷ 5 = 127 (✔)
• 357 ÷ 7 = 51 (✔)
• 572 ÷ 11 = 52 (✔)
• 728 ÷ 13 = 56 (✔)
• 289 ÷ 17 = 17 (✔)

이제 위 조건을 만족하는 모든 팬디지털 숫자들을 찾아서 그 합을 계산하면 됩니다.

 

문제 자체는 팬디지털(0~9까지의 숫자를 한번씩만 쓴 숫자)의 부분 문자열이 특정 소수로 나누어지는 가를 판별하면 됩니다.

 

가장 손쉽게 구현할 수 있는 방법은 백트랙킹(back tracking) 방법을 사용합니다.

속도를 조금이라도 빠르게 하기 위해서 숫자를 만들 때, 세개의 숫자를 쓰는 것이 아니라, 기존의 값에 10을 곱한 후 새로운 값을 더하는 방식으로 구현했습니다. (사실 그다지 이것에 의해서 속도 차이가 발생하지는 않을겁니다.)

간단한 형태의 자기호출 함수를 사용해서 만들었습니다.

 

sub-string divisibility

 

제가 작성한 소스 코드입니다.

//------------------------------------------------
//    Project Euler #43 - Sub-string Divisibility
//        - by Aubrey Choi
//        - created at 2015-03-29
//------------------------------------------------
#include <stdio.h>
#include <stdint.h>

uint64_t SumPD(uint64_t n, int mask, int t);

int main()
{
    printf("Ans = %ju\n", SumPD(0, 0, 0));
}

uint64_t SumPD(uint64_t n, int mask, int t)
{
    const int p[] = { 1, 1, 1, 2, 3, 5, 7, 11, 13, 17 };
    if( t == 10 ) { printf("%ju\n", n); return n; }

    uint64_t sum = 0;
    for( int i = 0 ; i < 10 ; i++ )
    {
        if( (mask>>i)&1 ) continue;
        if( ((n*10+i)%1000)%p[t] ) continue;
        sum += SumPD(n*10+i, mask | (1<<i), t+1);
    }
    return sum;
}