[PE] Project Euler 55

프로젝트 오일러 55번에서는 Lychrel number라는 것에 대해 먼저 설명해준다.

 

예를 들어 47이 주어졌을 때 이를 뒤집은 74를 더하면 121이 되어 1회 시행만에 palindrome이 된다.

 

349의 경우

 

349+943=1292

1292+2921=4213

4213+3124=7337

 

즉, 3회 시행만에 palindrome이 된다.

 

Lychrel number는 이러한 뒤집기-더하기 시행을 아무리 반복해도 palindrome이 되지 않는 숫자를 뜻하는데, 이 문제에서는 10000보다 작은 숫자들 중에 이러한 뒤집기-더하기 시행을 50번 반복하는 동안 palindrome이 나오지 않으면 Lychrel number라고 친다 하고 이런 숫자가 몇 개나 있는지 구하라고 한다.

 

이 문제는 뒤집기-더하기 시행만 구현할 수 있으면 간단하게 풀린다.

sol = 0
for i in range(10000):
    cnt = 0
    j = i
    end = False
    while cnt<50:
        k = j + int(str(j)[::-1])
        if str(k) == str(k)[::-1]:
            end = True
            break
        j = k
        cnt+=1
    if not end: sol+=1
print(sol)

파이썬에서 주어진 정수를 뒤집기 위해서 다음의 과정을 거쳤다.

- 우선 int형 값을 string형으로 바꿔주고,

- 해당 리스트를 뒤집는다고 생각하여 [::-1]을 취해주고,

- 이 값을 int형으로 다시 바꿔준다.

 

그리고 palindrome임을 확인하기 위해 int형 값을 string으로 변환한 것과 string으로 변하고 뒤집은 것의 값이 같은지 체크해주었다.

 

이 과정을 50번 거쳐도 palindrome check를 통과하지 못하면 solution 값에 1을 더하면 된다.