프로젝트 오일러 #55 라이크렐 수

이번 문제도 난이도 5% 문제입니다.

 

라이크렐 수는 어떤 양의 정수가 있다면, 그 정수를 10진수로 표현했을 때, 역순으로 표시된 수와의 합이 대칭수가 되는 가입니다.  대칭수가 되지 않으면, 마찬가지로 역순의 수와 더합니다.

 

이론상으로는 점점 증가하는 수이므로, 언젠가 확률적으로 대칭수(역순으로 표시해도 자기 자신이 되는 수)가 될 수 있습니다.

 

증명은 되지 않았지만, 무한히 시행해도 대칭수가 만들어지지 않는 수가 있다고 하고, 그 수들을 라이크렐 수라고 부릅니다.  그리고 그런 수중에 가장 작은 수가 196이라고 알려져 왔습니다.  문제는 얼마나 많이 시행을 하는 가에 따라서, 라이크렐 수라고 생각한 수가 라이크렐 수가 아닐 수도 있습니다.

 

 

그래서 이 문제에서는 시행횟수가 50번까지 안 되면 라이크렐 수라고 규정을 했습니다.  53번째 만들어진 수도 예가 들어져 있지만요.

 

문제에서는 대칭수중에 라이크렐 수가 존재한다는 것입니다.  그러한 대칭수들의 갯수가 10,000 이하 중에 몇개가 존재하는 가가 이 문제의 질문입니다.

 

이 문제를 풀기 위해서는 그냥 C/C++로 뚝딱뚝딱 짤 수가 없습니다.  왜냐하면 역순의 수를 더한다는 것은 평균 2배를 하는 것과 같다고 볼 수 있습니다.  그러면 2의 50승까지 연산을 해야 하는데, 32비트, 64비트 정수형을 이용해서 풀 수는 없습니다.  128비트 정수형이 있다면 가능하겠죠.

 

그래서 쉽게 짜려면, 파이썬 등으로 짜는 것이 좋습니다.

 

전 두가지 버전으로 다 작성을 해보았습니다.

 

일단 C/C++ 버전 코드입니다.

 

#include <stdio.h>
#include <string.h>
#include "NxBigInt.h"

NxBigInt GetReverse(NxBigInt n);
bool IsLychrel(int n);

int main()
{
    int count = 0;
    for( int k = 1 ; k < 10000 ; k++ )
        if( IsLychrel(k) ) count++;
    printf("ans = %d\n", count);
}

NxBigInt GetReverse(NxBigInt n)
{
    NxBigInt s = 0;
    while( n )
    {
        int r;
        n.DivideAndStoreRemain(10, &r);
        s *= 10;
        s += r;
    }
    return s;
}

bool IsLychrel(int n)
{
    NxBigInt s = n;
    s += GetReverse(s);
    for( int i = 1 ; i < 50 ; i++ )
    {
        NxBigInt r = GetReverse(s);

        if( s == r ) return false;
        s += r;
    }
    return true;
}

 

 

이것은 위의 알고리즘을 그대로 채용한 파이썬 코드입니다.

 

def Reverse(n):
    q = n
    s = 0
    while( q > 0 ):
        s = s*10 + q%10
        q = q / 10
    return s

def IsLychrel(n):
    n = n + Reverse(n)
    for i in range(1, 50):
        r = Reverse(n)
        if( r == n ): return False
        n = n + r
    return True

count = 0
for k in range(1, 10000):
    if( IsLychrel(k) ): count = count+1
print count

 

 

실행시간은 파이썬은 6배정도 느리네요.  아무래도 스크립트 언어다보니 어쩔 수 없나봅니다.  코드의 간결성은 파이썬이 더 좋죠.