[프로젝트 오일러] 문제4 - 가장 큰 대칭수

문제

영문

Largest palindrome product

A palindromic number reads the same both ways. The largest palindrome made from the product of two 2-digit numbers is 9009 = 91 × 99.

Find the largest palindrome made from the product of two 3-digit numbers.

바로가기

 

한글

앞에서부터 읽을 때나 뒤에서부터 읽을 때나 모양이 같은 수를 대칭수(palindrome)라고 부릅니다.
두 자리 수를 곱해 만들 수 있는 대칭수 중 가장 큰 수는 9009 (= 91 × 99) 입니다.

세 자리 수를 곱해 만들 수 있는 가장 큰 대칭수는 얼마입니까?

바로가기

 

해설

수학적 해석

xyzzyx (단, x, y, z는 일의 자리 수)

 

세자리 수 곱하기 세자리 수를 해서 나온 가장 큰 대칭수는 적어도 6자리 숫자일겁니다. 그러면 다음과 같은 모습이겠지요.

 

P = 100000x + 10000y + 1000z + 100z + 10y + x
= 100001x + 10010y + 1100z
= 11(9091x + 910y + 100z)

 

해당 수를 수식으로 정리해서 살펴보면 항상 11의 배수가 됨을 확인할 수 있습니다. 그러니 둘 중 하나의 수는 무조건 11의 배수입니다!

 

파이썬 (Python)

def isPalindrome(n):
  n_test = n
  reversed = 0

  while (n_test > 0):
    reversed = 10*reversed + n_test%10
    n_test = n_test//10

  return (n == reversed)

우선 다음과 같이 대칭수인지 아닌지를 따져보는 함수를 짜봅시다. n을 입력받으면 n을 거꾸로 한 수인 reversed를 구하고, n과 reversed가 같은지 아닌지 확인합니다. 만약 대칭수라면 이 둘이 같겠지요!

 

max_palindrome = 0

for a_div11 in range(90,10,-1): # 90*11 = 990
  for b in range(999,100,-1):
    mul_ab = 11*a_div11*b
    if mul_ab < max_palindrome:
      break
    if isPalindrome(mul_ab) :
      max_palindrome = mul_ab

print(max_palindrome)

 그 후 다음과 같이 이중 반복문으로 모든 경우의 수를 확인해줍시다. a는 11의 배수라 가정하고, 11로 나누어준 수로 반복문을 돌려줍시다. 곱이 지금까지중 가장 큰 대칭수보다 작으면 반복문을 나옵니다. 지금까지 찾은 대칭수보다 더 큰, 새로운 대칭수가 나오면 저장해줍시다. 반복문을 끝내고 남아있는 수가 가장 큰 대칭수입니다!

 

C

#include<stdio.h>
int main(void) {
	int n1, n2, n3;
	int a=989, a1, a2, a3;
	int i = 90;
	// 9091a+910b+100c가 i로 나누어지는지 보이고 싶음
	while (i >= 10) {
		n1 = 9091 % i;
		n2 = 910 % i;
		n3 = 100 % i;
		a = 999;
		while (a >= 100) {
			a1 = a / 100;
			a2 = (a / 10) % 10;
			a3 = a % 10;
			if ((n1*a1+n2*a2+n3*a3) % i == 0 && (9091 * a1 + 910 * a2 + 100 * a3) / i <= 999) {
				break;
			}
			a--;
		}
		if (a >= 100) {
			printf("%d * %d = %d\n", 11 * i, (9091 * a1 + 910 * a2 + 100 * a3) / i, 1000 * a + 100 * a3 + 10 * a2 + a1);
		}
		i--;
	}
}

 제가 처음에 풀었던 방식입니다. 특이하게 직접 대칭 수인지 확인하지 않고, 위의 수학적 해석에서 따져봤던 9091x + 910y + 100z를 만족하는지를 체크하고 있습니다.

 

정답

906609