43. 프로젝트 오일러 #43 : 부분 문자열 나누어 떨어지기

이번 문제도 간단한 문제입니다.  (난이도 5%)

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

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

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

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

소스에 대한 설명은 굳이 필요하지는 않을 듯 하네요.

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