[C++/Python] 프로젝트 오일러 #56 : 제곱수의 자릿수 합

이 문제는 난이도 5% 문제이지만, BigInt 모듈이 없는 언어 사용자는 해당 모듈을 구해야 하는 어려움이 있습니다.  파이썬, 자바, C#과 같이 BigInt 모듈이 있는 프로그래밍 언어 등을 이용하면 간단하게 해결할 수 있습니다.

 

 

문제는 간단합니다.

a, b < 100 안에서 a의 b제곱한 결과를 10진수로 표현할 때, 모든 자릿수의 합 중 최대값을 찾으라는 것입니다.  최소값은 1인 것은 당연하고요.  예를 들어서 a=13, b = 17 이라고 해보죠.  $a^b=8650415919381337933$이 됩니다.  총 자릿수가 19자리이니까, 10자리까지 표현할 수 있는 32비트 정수형으로는 계산이 불가능하죠.  각 자릿수의 합은 88입니다.  바로 이 자릿수의 합이 최대가 되는 수를 구하는 것이 목표입니다.

 

calculating power number

 

좀 더 좋은 알고리즘을 찾는다는 것은 어려울 것 같습니다.  그냥 무식한 방법으로 풀어보았습니다.

프로그램의 관건은 C/C++에서는 Big Integer 라이브러리를 사용하거나, 간단한 형태로 Big Integer를 구현하면 됩니다.

제 경우에는 직접 만들어 보았습니다.

 

아래는 제가 만든 소스입니다.

//------------------------------------------------
//    Project Euler #56 - Powerful Digit Sum
//        - by Aubrey Choi
//        - created at 2015-07-24
//------------------------------------------------
#include <stdio.h>
#include <time.h>

struct BigInt
{
    BigInt(int m)
    {
        len = 0;
        while(m)
        {
            v[len++] = m%10;
            m /= 10;
        }
    }
    void mul(int s)
    {
        int c = 0;
        for(int i = 0; i < len; i++)
        {
            c += v[i]*s;
            v[i] = c%10;
            c /= 10;
        }
        while(c)
        {
            v[len++] = c%10;
            c /= 10;
        }
    }
    int sum()
    {
        int s = 0;
        for(int i = 0; i < len; i++) s += v[i];
        return s;
    }
    int len;
    char v[256];
};

void solve1()
{
    int v = 9, a, b;

    for( int i = 2 ; i < 100 ; i++ )
    {
        BigInt m = i;
        for( int j = 2 ; j < 100 ; j++ )
        {
            m.mul(i);
            int sum = m.sum();
            if( sum > v ) { v = sum; a = i; b = j; }
        }
    }
    printf("Ans = %d, (a = %d, b = %d)\n", v, a, b);
}

int main()
{
    clock_t t;

    t = clock();

    solve1();

    printf("Elapsed time is %.3f seconds \n", (float)(clock()-t)/CLOCKS_PER_SEC);
}

 

파이썬 버전은 훨씬 간단합니다.

#------------------------------------------------------------
#    Project Euler #56 - Powerful Digit Sum
#    Author: Aubrey Choi
#    Date:    2015.09.24.
#------------------------------------------------------------
v = [ sum(map(int, str(a**b))) for a in range(1, 100) for b in range(1, 100) ]
print(max(v))