[C++]프로젝트 오일러 16번 문제&풀이 (2의 1000승의 각 자릿수를 모두 더하면?)

문제 16번

2^15 = 32768 의 각 자릿수를 더하면 3 + 2 + 7 + 6 + 8 = 26 입니다.

21000의 각 자릿수를 모두 더하면 얼마입니까?

 

접근방법

1. 2의 1000승을 계산 한 후 10씩 나누어 더하려고 하면, 담을 수 있는 연산자가 없기 때문에 풀 수 없다.

2. 1부터 시작해서 2씩 곱해 갈 때 바로바로 자릿수를 구하여, 각 자릿수를 벡터에 거꾸로 담는다.

   (벡터는 뒤에서부터 숫자가 담기기 때문 /  모든 값을 0으로 시작하고, 첫번째 위치에 1을 담고 시작한다.)

3. 각 자릿수를 2를 곱했을 때, 10을 넘지 않는 경우와 / 넘는 경우 2가지로 나눈다.

  (10을 넘는 경우, 그 칸에는 10으로 나눈 나머지를 넣고, 옆칸에 1을 더한다)

 

2^10까지만 해보면

 

2^0 : 1 / 0 / 0 / 0 / 0 / 0 / 0 / 0 / 0 / 0  = 1

2^1 : 2 / 0 / 0 / 0 / 0 / 0 / 0 / 0 / 0 / 0 = 2

2^2 : 4 / 0 / 0 / 0 / 0 / 0 / 0 / 0 / 0 / 0 = 4

2^3 : 8 / 0 / 0 / 0 / 0 / 0 / 0 / 0 / 0 / 0 = 8

2^4 : 6 / 0 / 0 / 0 / 0 / 0 / 0 / 0 / 0 / 0 = 16

           +1

2^5 : 2 / 2 / 0 / 0 / 0 / 0 / 0 / 0 / 0 / 0 = 32

           +1

2^6 : 4 / 6 / 0 / 0 / 0 / 0 / 0 / 0 / 0 / 0 = 64

2^7 : 8 / 2 / 0 / 0 / 0 / 0 / 0 / 0 / 0 / 0 = 128

                +1

2^8 : 6 / 4 / 2 / 0 / 0 / 0 / 0 / 0 / 0 / 0 = 256

           +1

2^9 : 2 / 0 / 4 / 0 / 0 / 0 / 0 / 0 / 0 / 0 = 512

           +1 +1

2^10 : 4 / 2 / 0 / 1 / 0 / 0 / 0 / 0 / 0 / 0 = 1024

                      +1

 

#include <iostream>
#include <vector>

using namespace std;

int main()
{
    int count = 0;
    int sum = 0;
    int space = 500;

    vector<int> num_vec(space);
    num_vec[0] = 1;
    
    while (count < 1000)
    {
        for (int i = (space-1); i >= 0; i--)
        {
            if (num_vec[i] * 2 < 10)
            {
                num_vec[i] *= 2;
            }
            else
            {
                num_vec[i] = (num_vec[i] * 2) % 10;
                num_vec[i + 1] += 1;
            }
        }
        count++;
    }

    for (int i = 0; i < num_vec.size(); i++)
    {
        sum += num_vec[i];
        //cout << num_vec[i] << endl;
    }

    cout << "Answer is : " << sum << endl;

    return 0;
}

참고

https://github.com/mannlim/ProjectEuler

mannlim/ProjectEuler