4. 프로젝트 오일러 #4 : 가장 큰 대칭수 구하기

이번 문제는 간단하게 생각하면,

 

세자리수 a, b를 곱한 수가 대칭수인가 판단하면 된다고 할 수 있습니다.

 

그러나 그럴 경우 세자리수 x 세자리수의 갯수가 1억개정도 나오게 되죠.  그것에 대한 대칭수를 판단하는 것은 문제가 있을 수 있습니다.

 

그래서 제가 구현한 알고리즘은, 

1) 세자리수 x 세자리수 해서 나올 수 있는 가장 큰 대칭수부터 차례대로 발생시키고 (최대 900개)

2) 그 수들이 세자리수의 곱으로 표현되는가 (최대 900개)

 

결국 첫번째와 두번째가 오더가 비슷하지 않는가 하겠지만, 실제로는 많은 차이가 있습니다.

 

첫번째 알고리즘은 최댓값을 구하는 과정이 다시 필요합니다.  그러나 두번째 알고리즘은 첫번째 매칭이 되는 결과가 최댓값이 됩니다.

 

프로그램을 표시하자면, 아래와 같습니다.  세자리수 곱하기가 가능한 가를 판단하는 for 루프는 예상외로 적습니다.  대칭수의 크기가 작을 수록 많이 줄어드니까요.  실제로 제곱근이기 때문에 최대 900개가 아닙니다.  훨씬 더 적다고 볼 수 있죠.

 

 

int main()
{
    for( int n = 997 ; n > 100 ; n-- )
    {
        int v = n * 1000 + (n/100) + ((n/10)%10)*10 + (n%10)*100;
        for( int i = (v+998)/999 ; i*i <= v ; i++ )
        {
             if( v%i == 0 )
             {
                 printf("%dx%d = %d\n", i, v/i, v);
                 return 0;
             }
        }
    }
}