앞에서부터 읽을 때나 뒤에서부터 읽을 때나 모양이 같은 수를 대칭수(palindrome)라고 부릅니다.
두 자리 수를 곱해 만들 수 있는 대칭수 중 가장 큰 수는 9009 (= 91 × 99) 입니다.
세 자리 수를 곱해 만들 수 있는 가장 큰 대칭수는 얼마입니까?
Keyword : 대칭수
두 자리 수 곱셉의 대칭수 ( 100 ~ 9801 )
1000 이상이라고 가정하면 대칭수는 ?
= 1000*a + 100*b + 10*b + a
= 1001*a + 110*b
= 7*11*13*a + 2*5*11*b
= 11*(7*13*a + 2*5*b)
< a = 9, b = 0 > ==> (7*13) * (11*9) = 91 * 99 = 9009
세 자리 수 곱셉의 대칭수 ( 10000 ~ 998001 )
100000 이상이라고 가정하면 대칭수는 ?
= 100000*a + 10000*b + 1000*c + 100*c + 10*b + a
= 100001*a + 10010*b + 1100*c
= 11*9091*a + 11*910*b + 11*100*c
C / C++
int number; // number는 100000 이상이라 가정하고 998001(=999*999) 이하이다.
int a = 1; // a = 1 ~ 9
int b = 0; // b = 0 ~ 9
int c = 0; // c = 0 ~ 9
// 대칭수의 소인수는 11을 무조건 포함한다. 따라서 둘중 한 수는 세 자리 수 이며 11의 배수
// 따라서 multiplier = 10 ~ 90 --> 11 * multiplier = 110 ~ 990
int multiplier;
int m;
// 결과저장 변수들
int first;
int second;
int result;
while ( a<10 ) // c=0~9, b=0~9, a=1~9 까지의 루프
{
number = 11*(9091*a + 910*b + 100*c); // 해당 대칭수
multiplier = 9; // 11을 포함하는 대칭수의 약수를 구하기 위한 곱셈 값
while ( multiplier++ < 90 )
{
m = 11*multiplier;
if ( !(number % m) ) // 11을 포함하는 대칭수의 약수를 찾음
{
if ( number / m > 999 ) break; // 나머지 다른 수가 999 이하인가?
first = m;
second = number / m;
}
}
// c~b~a 차례대로 증가를 위함.
if ( !(++c %= 10) )
if ( !(++b %= 10) )
a++;
}
result = first * second;
cout << "Question 4 : " << first << " * " << second << " = " << result << endl;
