56. 프로젝트 오일러 #56 : 제곱수의 자릿수 합

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

문제는 간단합니다.  a, b < 100 안에서 a의 b제곱한 결과를 10진수로 표현할 때, 모든 자릿수의 합 중 최대값을 찾으라는 것입니다.  최소값은 1인 것은 당연하고요.

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

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

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

    for( int i = 2 ; i < 100 ; i++ )
    {
        NxBigInt m = i;
        for( int j = 2 ; j < 100 ; j++ )
        {
            m *= i;
            uint8_t s[1000];
            int len = m.ConvertToArrayLE(s, 1000);
            int sum = 0;
            for( int k = 0 ; k < len ; k++ )
                sum += s[k];
            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);
}