16. 프로젝트 오일러 #16 : 2의 1000승의 모든 자릿수 합 구하기.

사실 이번 프로그램은 Big integer를 사용할 줄 아느냐 아니냐에 따라서 달라진다고 봅니다.

많은 언어가 기본으로 Big Integer를 지원하기 때문에, 언어에 따라서 구현 난이도도 차이가 많을겁니다.

예를 들어서 python을 이용하면, 가볍게 이 문제를 해결할 수 있습니다.

>>> 2**1000

10715086071862673209484250490600018105614048117055336074437503883703510

51124936122493198378815695858127594672917553146825187145285692314043598

45775746985748039345677748242309854210746050623711418779541821530464749

83581941267398767559165543946077062914571196477686542167660429831652624

386837205668069376L

C/C++을 이용하기 위해서는 별도의 Big Integer 라이브러리를 이용하시거나 직접 해당 라이브러리와 비슷한 것을 작성하셔야 합니다.

제 경우에는 오래전부터 작성했던 Big Integer 라이브러리가 있었는데, 그동안 다른 일에 밀려서 손을 놓았던터라, 이번에 프로그램을 좀 작성했습니다.

이번 프로그램은 어떤 Big Integer 프로그램을 이용하든 별반 다를 것 없을거라 생각합니다.

제가 작성한 프로그램 코드는 다음과 같습니다.

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

int main()
{
        NxBigInt c = 1;

        c <<= 1000;

        uint8_t buf[1024];
        int k = c.ConvertToArray(buf, 1024);
        int sum = 0;
        for( int i = 0 ; i < k ; i++ )
        {
                sum += buf[i];
        }
        printf("Ans = %d\n", sum);
}

2의 1000승을 매번 2를 1000번 곱하시는 분들도 계시던데, 1000비트만큼 쉬프트 연산을 하는 것이 더 유리합니다.  물론 Big Integer 라이브러리가 그것을 지원하지 않는다면, 어쩔 수 없겠지만요.

ConvertToArray 함수는 Big Integer 수를 배열로, 지정된 진법(radix 기본값이 여기서는 10)으로 변환해서 저장합니다.  보통은 문자열로 만들지만, 여기서는 계산에 더 편리한 방법을 택했습니다.