오일러 프로젝트 55 번은 라이크렐 수를 구하는 것이다. 대칭수가 될 때까지 뒤집은 숫자를 더해서 비교하는 과정이 들어가기 때문에 BigNumber를 쓰는 것보다 좀 더 깔끔하게 진행하는 것이 좋겠다. 참고로 라이크렐 수는 아직 증명된 것은 아니고, 문제에서는 특정한 가정을 두고 서술된다.
47이란 숫자를 골라서 뒤집은 다음 다시 원래 수에 더하면 47 + 74 = 121과 같이 대칭수(palidrome)가 됩니다. 물론 모든 숫자가 이토록 쉽게 대칭수를 만들어내지는 않습니다. 예를 들어 349의 경우에는
349 + 943 = 1292
1292 + 2912 = 4213
4213 + 3124 = 7337
위에서 보는 것처럼 3번의 반복과정을 거쳐야 대칭수가 됩니다. 196과 같은 몇몇 숫자들은 이와 같은 과정을 아무리 반복해도 대칭수가 되지 않을 것이라고 추측되는데, 이런 수를 라이크렐 수라고 부릅니다. 아직 증명되지는 않았지만, 문제 풀이를 위해서 일단 라이크렐 수가 존재한다고 가정을 하겠습니다.
또한 1만 이하의 숫자들은 50번 미만의 반복으로 대칭수가 되든지 라이크렐 수이든지 둘 중 하나라고 합니다. 1만을 넘어서면 10677에 이르렀을 때 비로소 53번의 반복으로 4668731596684224866951378664라는 28자리의 대칭수가 만들어집니다.
그러면 1만 이하에는 몇 개의 라이크렐 수가 존재합니까? (http://euler.synap.co.kr/prob_detail.php?id=55)
접근
문제가 무시무시해보이는데, 사실 별 거 없다. 1) 원래의 숫자를 뒤집는다. 2) 원래의 값과 더한다. 3) 대칭수인가? 4) 1~3을 50회반복한다. 그 사이에 대칭수가 발견되면 fail, 50번을 반복해도 발견되지 않으면 pass 하여, 이 테스트를 통과한 숫자들만 세면 된다.
문제는 이런 식으로 수십자리로 올라가는 큰 수를 다뤄야 하는데, 여기서 BigNumber를 쓸 것이냐?하는 생각이 든다. 그런데 BigNumber를 써서 뒤집는 것은 description 을 구해서 뒤집고 이를 통해서 새 값을 만들고 다시 둘을 더하고, 그 결과의 description을 얻어서 대칭인지 검사해야 한다. 이는 제법 귀찮은 요소들을 포함하고 있다. 따라서 1자리 숫자로 이루어진 배열로 정수를 표현하도록 하자.
// 숫자를 1자리 정수배열로 분해하는 함수
func parseNum(_ n: Int) -> [Int] {
var (n, temp) = (n, Array<Int>())
while n > 0 { temp.append(n % 10); n /= 10 }
return temp
}
// 숫자를 뒤집어서 더하는 처리
func process(_ a: [Int]) -> [Int] {
var temp: [Int] = []
var flag = 0
for (i, x) in a.enumerated() {
var v = x + a[a.count - 1 - i] + flag
if v > 9 { (flag, v) = (v / 10, v % 10) }
else { flag = 0 }
temp.append(v)
}
if flag > 0 { temp.append(flag) }
return temp
}
// 라이크렐 수 테스트
func test(_ n: Int) -> Bool {
var a = parseNum(n)
main: for _ in 1..<50 {
a = process(a)
for i in 0..<(a.count / 2) where a[i] != a[a.count - 1 - i] {
continue main // 대칭수가 아니므로 다음루프로 진행해야 한다.
}
return false // 대칭수니까 fail
}
// 50번 검사했지만, 대칭수를 못찾았다. 성공
return true
}
print((1...10_000).filter(test).count)실행했을 때 결과는 0.1초 내외.
파이썬 풀이
사실 이 문제는 파이썬에 거의 특화되어 있다고 봐도 된다. 모든 부분부분들이 매우 간단하게 작성된다. (그리고 엄청 빠르다.)
def test(n):
for _ in range(50):
n += int(str(n)[::-1])
s = str(n)
if s == s[::-1]:
return False
return True
def e055():
print(sum(1 for x in range(1, 10_000 + 1) if test(x)))