[C/C++] 프로젝트 오일러 #32 : 팬디지털 곱

프로젝트 오일러 #32 문제는 어려움 정도가 5%라 상당히 난이도가 낮은 문제네요.

 

팬디지털 숫자란 특정 범위의 모든 숫자를 한 번씩만 사용하여 구성된 숫자입니다. 예를 들어, 1부터 9까지의 숫자를 모두 한 번씩 포함한 조합(예: 123456789, 391867254 등)은 팬디지털이라고 부릅니다. 이 문제에서는 1부터 9까지의 숫자를 정확히 한 번씩만 사용해야 한다는 조건이 주어집니다.

문제의 목표는 1부터 9까지의 숫자를 사용해 \(a \times b = c\) 형태의 곱셈식을 만들고, a, b, c를 모두 이어 붙였을 때 1부터 9까지의 모든 숫자를 포함하도록 하는 조합을 찾는 것입니다. 예를 들어, \(39 \times 186 = 7254\)는 39, 186, 7254를 합쳐 391867254라는 숫자를 만들며, 이는 1부터 9까지의 숫자를 정확히 한 번씩 사용했으므로 팬디지털 조건을 만족합니다.

조건을 만족하는 모든 곱셈 조합을 찾아서 c 값들을 모으고, 중복을 제거한 후 이 값을 모두 합산하는 것이 최종 목표입니다. 예를 들어, 가능한 c 값이 7254와 7632라면, 이들의 합인 14886이 답이 됩니다.

 

이 문제는 일단 다음과 같은 접근을 생각했습니다.

 

어떤 수 n이 있습니다.  이 수에 대한 약수를 구합니다.  그러면 두 수를 구할 수 있겠죠.  그러면 이 수에 대해서 팬디지털인지 검사하면 됩니다.

 

두 수를 먼저 만든 후 곱하는 것보다는 하나의 수에 대해서 인수분해를 하는 것이 복잡도가 덜하겠다는 생각이 들더라고요.

 

팬디지털을 검사하는 로직은 일단 간단하게 했습니다.  사실 이 부분이 제일 핵심이기도 하고요.  팬디지털은 비트플래그를 이용합니다. 비트플래그에 중복이 생기면 팬디지털이 아닌 것이 되고요.  모두 다 체크되었다면 완벽하게 팬디지털이 되겠죠.

 

pan digital

 

팬디지털인지 검사하기 위해서 검사하는 로직은 다음과 같습니다.  첨부된 소스는 참고용으로만 봐주세요.

 

//------------------------------------------------
//    Project Euler #32 - Pandigital Products
//        - by Aubrey Choi
//        - created at 2015-02-04
//------------------------------------------------
#include <stdio.h>

bool IsPanDigital(int n);

inline bool Check(int &k, int q)
{
    while( q )
    {
        int c = q%10;
        if( c == 0 || (k & (1<<c)) ) return false;
        k |= 1<<c;
        q /= 10;
    }
    return true;
}

int main()
{
    int sum = 0;

    for( int i = 1234 ; i <= 98765 ; i++ )
        if( IsPanDigital(i) ) sum += i;
    printf("Ans = %d\n", sum);
}

bool IsPanDigital(int n)
{
    int k = 0;

    if( Check(k, n) == false ) return false;

    for( int i = 2 ; i*i < n ; i++ )
    {
        if( n%i ) continue;
        int u = k;
        if( Check(k, n/i) && Check(k, i) && k == 0x3fe )
        {
            printf("%dx%d=%d\n", i, n/i, n);
            return true;
        }
        k = u;
    }
    return false;
}

Check 작업이 완료되면, 마지막에는 비트플래그가 0x3fe 라면 팬디지털이 완성됩니다.