[C++/Python] 프로젝트 오일러 #55 라이크렐 수

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

 

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

 

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

 

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

 

 

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

 

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

 

reverse sum

 

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

 

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

 

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

 

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

 

//------------------------------------------------
//    Project Euler #55 - Lychrel Numbers
//        - by Aubrey Choi
//        - created at 2015-03-31
//------------------------------------------------
#include <stdio.h>
#include <string.h>

struct BigInt
{
    BigInt(int n)
    {
        len = 0;
        while(n)
        {
            v[len++] = n%10;
            n /= 10;
        }
    }
    int len;
    char v[100];
};

BigInt ReverseSum(BigInt &n)
{
    BigInt s = 0;
    int c = 0;
    for(int i = 0; i < n.len; i++)
    {
        c += n.v[i] + n.v[n.len-i-1];
        s.v[s.len++] = c%10;
        c /= 10;
    }
    if(c) s.v[s.len++] = c;
    return s;
}

bool IsPalindrome(BigInt &n)
{
    for(int i = 0; i < n.len/2; i++)
    {
        if(n.v[i] != n.v[n.len-i-1]) return false;
    }
    return true;
}

bool IsLychrel(int n)
{
    BigInt s = n;
    for( int i = 1 ; i < 50 ; i++ )
    {
        s = ReverseSum(s);
        if(IsPalindrome(s)) return false;
    }
    return true;
}

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

 

 

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

 

#------------------------------------------------------------
#    Project Euler #55 - Lychrel Numbers
#    Author: Aubrey Choi
#    Date:    2015.03.31.
#------------------------------------------------------------
def Reverse(n):
    return int(str(n)[::-1])

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

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

 

 

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