(C언어, 파이썬)프로젝트 오일러(Project Euler)16.2^1000의 각 자리수를 모두 더하면?

2¹⁵ = 32768 의 각 자리수를 더하면 3 + 2 + 7 + 6 + 8 = 26 입니다.
2¹⁰⁰⁰의 각 자리수를 모두 더하면 얼마입니까?

---

1. 파이썬

a = str(2**1000)
sum = 0
for i in range(len(a)):
    sum += int(a[i])

print(sum)

 

파이썬으로 구현하면 정말 쉬워진다.  2¹⁰⁰⁰을 문자열 형태로 저장하고, 문자열의 길이만큼 인덱스를 정수형태로 변환해 더하면 끝난다. 

 

2. C언어

 

#define SIZE 400
#include <stdio.h>

int main(void)
{
    int num[SIZE] = { 0 };
   num[SIZE - 1] = 1;
    int i, j, sum = 0;

    for (i = 1; i <= 1000; i++) {
        for (j = 0; j < SIZE; j++) {
            if (num[j] * 2 >= 10) {
                num[j - 1] = num[j - 1] + ((num[j] * 2) / 10);
                num[j] = (num[j] * 2) % 10;
            }
            else {
                num[j] = num[j] * 2;
            }
        }
    }
    for (i = 0; i < SIZE; i++)
       sum += num[i];

    printf("%d", sum);
    return 0;
}​

 

c언어 코드는 프로젝트 오일러 포럼에서 rudtjr7655 님의 코드를 참고했다.

2¹⁰⁰⁰은 정수 표현 범위를 벗어나므로 다른 형태로 저장해야 한다. 각 자리수를 배열 한 요소에 저장하면 된다.

num[399]는 일의 자리, num[398]은 십의 자리. 이런 식이다.

 

4번째 열에서 모든 배열을 0으로 초기화한다.

5번째 열에서 마지막 배열 요소를 1로 한다. 

 

외부 for문에서는 1000번 반복하여 제곱을 계산한다.

내부 for문에서 실질적인 계산을 수행한다.

 

num[j]에 2를 곱했을 때 10이 넘으면 받아올림하고, 아니면 2만 곱한다. 

 

python tutor에서는 1000회 이상 문장을 실행할 수 없기 때문에, 배열 크기를 10개로 줄였다. 사진에서 인덱스 9를 399로, 인덱스 8을 398로 보면 된다.

 

1: num[399]에 2를 곱한다. -> num[399] = 2

 

 

2: num[399]에 2를 곱한다. -> num[399] = 4

 

 

3: num[399]에 2를 곱한다. -> num[399] = 8

 

 

4: num[399] * 2 == 16이므로, num[398]에 16을 10으로 나눈 몫인 1이 저장되고, num[399]에 16을 10으로 나눈 나              머지인  6이 저장된다.

 

 

5: num[398]에 있는 1에 2를 곱한다.

 

 

6. num[399]에 있는 6에 2를 곱한다. 받아올림해서 1은 num[398]에 넘기고 num[399]엔 2를 저장한다.

 

이 과정은 

 

 

분배법칙을 이용해 계산했다고 볼 수 있다. 먼저 10 * 2를 수행한 후, 6 * 2를 수행해 값을 저장했다.

 

이렇게 1000번을 수행하고 나면 2¹⁰⁰⁰의 각 자릿수가 배열에 저장된다.

 

이제 각 요소를 sum에 모두 더해 출력하면 된다.

 

정답: 1366