36. Double-base palindromes

1. 개요

문제는 이곳에서 확인할 수 있다. 어떤 문자나 숫자의 역순이 원래의 것과 같다면 그 문자나 숫자를  palindrome이라고 한다. 585는 특이한 성질을 지니고 있는데 585와 그것의 2진수가 모두 palindrome이기 때문이다. 이와 같은 성질을 지닌 1,000,000 이하의 숫자의 합을 구하는 것이 문제의 목표이다.

2. 구현

어떤 수의 palindrome을 구하는 방법에는 여러가지가 있는데, 여기서는 나눗셈을 이용한 방법을 사용한다. 예를 들어, 115를 10으로 나누면 11의 몫과 5의 나머지가 나온다. 5에 10을 곱하여 이를 결과라고 하자. 11을 10으로 나누면 몫 1과 나머지 1이 나온다. 앞서 구한 결과에 10을 곱한 후 나머지 1에 10을 곱하여 결과에 더한 후 몫 1을 거기에 더하면 511이 되어 palindrome을 구할 수 있다.

흥미로운 것은 위의 과정에서 10을 2로 대체하면 115의 이진수의 palindrome의 10진수가 된다는 점이다. 이를 이용하여 구현한다.

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24

# -*- coding: utf-8 -*-   n = 3   def make_reverse(n, base):       reversed_n = 0     n, r = divmod(n, base)       while n != 0:         reversed_n = (reversed_n + r) * base         n, r = divmod(n, base)        reversed_n += r           return reversed_n   result = 0   for i in range(1,1000001):     if i == make_reverse(i, 10) and i == make_reverse(i, 2):         print (i)         result += i     print('RESULT :', result)

답은 872187이다.