[C++]프로젝트 오일러 20번 문제&풀이 (100! 의 자릿수를 모두 더하면?)

문제 20번

n! 이라는 표기법은 n × (n − 1) × ... × 3 × 2 × 1을 뜻합니다.

예를 들자면 10! = 10 × 9 × ... × 3 × 2 × 1 = 3628800 이 되는데,
여기서 10!의 각 자릿수를 더해 보면 3 + 6 + 2 + 8 + 8 + 0 + 0 = 27 입니다.

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

 

접근방법

1. 파이썬으로 하면 간단하겠으나, C++는 자료형을 고려해서 풀어야 하기 때문에 조금 번거롭다.

2. 충분히 긴 벡터(numVector(200))를 만들고, 첫번째 자리에 1을 넣는다.

3. 벡터의 각 요소에 각 자리수가 들어가도록 할건데, 숫자를 그대로 넣고 10으로 나눠서 나머지는 남기고, 몫은 한칸씩 옆으로 보내 더해준다.(1의자리수가 numVector[0]에, 10의 자리수가 numVector[1]에 담기는 방식)

4. 101을 예시로 들어보면 10으로 나눴을 때 나머지(1)를 첫번째 자리(numVector[0])에 남기고, 몫(10)을 그 다음칸(numVector[1])으로 넘긴다. 두번째 자리(numVector[1])도 10보다 크거나 같으므로, 10으로 나눠보면 0을 두번째 자리(numVector[1])에 남기고, 몫(1)을 세번째 자리(numVector[2])로 넘긴다.

5. 위와 같은 방식으로 1~100의 모든 수를 곱하면서 벡터의 각 요소가 각 자리수를 담도록 하면 된다.

#include <iostream>
#include <vector>

using namespace std;

int main()
{
	vector<int> numVector(200);

	numVector[0] = 1;
	int sum = 0;

	for (int num = 100; num > 1; num--)
	{
		for (int n = 0; n < numVector.size(); n++)
		{
			numVector[n] *= num;
			//cout << numVector[n] << " ";
		}
		//cout << endl;

		for (int n = 0; n < numVector.size() - 1; n++)
		{
			if (numVector[n] >= 10)
			{
				numVector[n + 1] += (int)(numVector[n] / 10);
				numVector[n] = numVector[n] % 10;
			}
		}

		/*for (int n = 0; n < numVector.size(); n++)
		{
			cout << numVector[n] << " ";
		}
		cout << endl;
		cout << endl;*/
	}

	for (int n = 0; n < numVector.size(); n++)
	{
		sum += numVector[n];
	}

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

	return 0;
}

참고

https://github.com/mannlim/ProjectEuler

mannlim/ProjectEuler