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

Project Euler 문제 38번에서는 “팬디지털 수”와 “곱셈 연산”의 개념을 활용하여 특정 조건을 만족하는 가장 큰 수를 찾는 것이 목표입니다. 팬디지털 수란 각 숫자가 1부터 9까지 한 번씩만 등장하는 수를 의미합니다. 예를 들어, 192384576은 1부터 9까지의 숫자가 모두 포함되어 있으므로 팬디지털 수라고 할 수 있습니다.

 

문제에서는 특정 정수 n 과 정수 k 를 선택하여, \( n \times 1 \), \( n \times 2 \), \( n \times 3 \), …, \( n \times k \)로 만들어진 수를 이어붙였을 때 팬디지털 수가 되는지를 확인하도록 요구하고 있습니다. 또한, 이 과정에서 만들어질 수 있는 가장 큰 팬디지털 수를 구하는 것이 목표입니다.

 

예를 들어, n = 192 이고 k = 3 일 때, \(192 \times 1 = 192 \), \(192 \times 2 = 384 \), \(192 \times 3 = 576 \)을 계산하고, 이를 이어붙이면 192384576이 됩니다. 이 값은 팬디지털 수이므로 조건을 만족합니다.

 

문제의 핵심은 이러한 팬디지털 수 중에서 가장 큰 값을 찾는 것이며, n 과 k 의 범위를 적절히 탐색하여 최적의 값을 도출하는 알고리즘을 설계하는 데 있습니다. 이를 통해 1부터 9까지 모든 숫자를 정확히 한 번씩 포함하며, 가능한 한 가장 큰 팬디지털 수를 계산하는 것이 최종 목표입니다.

 

난이도 5%에 해당하는 문제입니다.

최대값을 찾으라는 것이기 때문에, 4자리 숫자부터 차례대로 찾아서 x2 한 값과 원래의 값이 팬디지털을 이루는지만 검사하면 됩니다.

 

pandigital

 

 

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

//------------------------------------------------
//    Project Euler #38 - Pandigital Multiples
//        - by Aubrey Choi
//        - created at 2015-03-20
//------------------------------------------------
#include <stdio.h>

bool IsPandigitalMultiply(int n);

int main()
{
    int ans;
    for( ans = 9876 ; !IsPandigitalMultiply(ans) ; ans-- );
    printf("Ans = %d%d\n", ans, ans*2);
}

bool IsPandigitalMultiply(int n)
{
    unsigned short s = 0;
    for( int i = 1 ; ; i++ )
    {
        int t = n*i;
        while( t )
        {
            int p = t%10;
            if( p == 0 ) return false;
            t /= 10;
            if( s & (1<<p) ) return false;
            s |= 1<<p;
        }
        if( s == 0x3fe ) return true;
    }
    return false;
}

팬디지털이 되는지 검사하기 위해서 s라는 비트플래그 변수를 사용했습니다. 겹치는 숫자가 발생하면 당연히 팬디지털이 안될테고요. 모든 비트가 다 채워졌으면 0x3fe란 숫자가 되므로, 처리한 결과가 0x3fe가 되면 true를 반환합니다.

 

사실 원래수 자체가 겹치는 숫자가 있으면 안 되기 때문에 겹침이 없는 숫자(일반적으로 순열로 만들어진 수)를 이용하면 테스트하는 시간이 더 줄어들겠죠. 여기서는 간단하게 구현해보았습니다.