Problem #020

오일러 알고리즘

🚩 문제 설명

오일러 알고리즘 #020

◾ 100! 팩토리얼의 자릿수의 합을 구하는 문제이다.

n! (팩토리얼)
n! = n x (n-1) x ... x 2 x 1 

 

 

---

 

 

📑 문제 풀이

//20200302 Problem 020
#include <iostream>
#define LL long long
using namespace std;

const LL MAX = 100000LL;

LL num[MAX] = { 1, };

int main()
{
	int cnt = 0;

	for (int i = 1; i <= 100; i++)
	{
		for (int j = 0; j <= cnt; j++)
		{
			if (num[j] == 0) continue;

			num[j] = num[j] * i;
		}

		for (int j = 0; j < MAX; j++)
		{
			if (num[j] == 0) continue;

			if (num[j] >= 10)
			{
				num[j + 1] = num[j + 1] + (num[j] / 10);
				num[j] = num[j] % 10;
				cnt = j + 1;
			}
		}
	}

	int ans = 0;
	for (int i = 0; i < MAX; i++)
	{
		if (num[i] != 0)
		{
			ans += num[i];
			//cout << num[i];
		}
		else continue;
	}

	cout <<'\n'<< ans << '\n';
	return 0;
}

💬 Point

👉 Big Integer 문제
👉 자리 하나당의 수를 넣을 배열을 만들어준다.

◾ 첫번째 반복문은 1 ~ 100 까지 돈다.

◾ 두번째 반복문-1 에서부터 1 ~ 100 까지의 수를 곱해준다.

◾ 두번째 반복문-1 에서 만약 num[0]이 10이 넘어가면

◾ 두번째 반복문-2 에서 해당 십의 자리를 다음의 인덱스로 넘겨준다.

◾ 해당 과정으로 빅인티져를 구한다.

◾ 각 배열의 값이 10을 넘어가면 십의 자리를 다음으로 넘겨주고 일의 자리는 남기는 형식

 

 

---

 

 

But,

✅ 파이썬으로 풀면 더 간단한 코드로 풀 수 있는 것 같다.
✅ 굳이 cnt를 주지 않았어도 됐었을 듯.
✅ 첫번째 반복문을 MAX까지 돌렸어도 괜찮았을것같다.

➕ 풀이 사이트 참조

https://www.mathblog.dk/project-euler-20-sum-digits/

Project Euler 20: Sum of Digits in 100! in C# | MathBlog

 

 

 

 

 

 

 

 

 

 

 

---