프로젝트 오일러 문제 16

Power digit sum

Problem 16

2¹⁵ = 32768 and the sum of its digits is 3 + 2 + 7 + 6 + 8 = 26.

What is the sum of the digits of the number 2¹⁰⁰⁰?

2의 1000제곱의 각 자리 수를 모두 더할 경우 몇이 되는지 구하는 문제.
1. 필요한 만큼 배열을 할당한다. 
2. 아래에 기술한 내용을 지수만큼 반복한다.
 - 배열 각 요소에 2를 곱한다.
 - 값이 10 이상인 요소는 다음 자리에 10을 나눈 몫을 더해주고 나머지만 남긴다.
3. 배열에 있는 각 요소의 값을 모두 더한다.

int Problem016(int exponent)
{
	if (exponent < 0) 
	{
		return -1;
	}
	if (exponent == 0) 
	{
		return 1;
	}

	int * arrNum = new int[exponent + 1];
	arrNum[0] = 1;
	for (int i = 1; i <= exponent; i++)
	{
		arrNum[i] = 0;
	}

	for(int i = 1; i <= exponent; i++)
	{
		for (int j = 0; j < exponent; j++)
		{
			if (arrNum[j] == 0)
			{
				continue;
			}
			arrNum[j] *= 2;
		}
		for (int k = 0; k <= exponent; k++)
		{
			if (arrNum[k] == 0)
			{
				continue;
			}
			if (arrNum[k] >= 10)
			{
				arrNum[k + 1] += arrNum[k]/10;
				arrNum[k] %= 10;
			}
		}
	}

	int ret = 0;
	for (int i = exponent; i >= 0; i--) 
	{
		ret += arrNum[i];
	}
	return ret;
}