38. 프로젝트 오일러 #38 : 팬디지털 곱하기

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

이번 문제는 1부터 9까지의 숫자를 한번씩만 사용하는 문제입니다.

192라는 숫자를 예를 들자면,

192x1 = 192

192x2 = 384

192x3 = 576

이 되어서, 곱하기 결과 192, 384, 576의 숫자들을 합치면, 1부터 9까지 오직 한번씩만 사용된 팬디지털을 이룹니다.

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

프로그램은 간단합니다.

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를 반환합니다.

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