[C++] 백준 1676번 팩토리얼 0의 개수

이 문제는 팩토리얼이라는 소리를 듣자마자 분명 계산해서 푸는것은 아니라고 직감했다.

10!만 되도 30만이 넘어갈텐데(맞나.....?) 문명 입력되는 n의 크기가 커지면

아무리 long long을 써도 저장을 못할것 같았다.

string으로 접근하려고 했는데, 이것도 아닌것 같아서 고심을 해보았다.

결국 뒤의 0의 개수는 10이 몇번 나오는지에 따라 달렸다.

그러니까 팩토리얼을 계산할 필요 없이 그냥

n에서 2와 5가 얼마나 나오는지만 고민하면 되는 것이다.

제곱수일때만 생각을 해주면 되는 생각보다 간단한 문제였다.

#include <iostream>
#include <string>
using namespace std;

int main() {

	int n;
	int two = 0, five = 0;
	cin >> n;

	for (int i = 2; i <= n; i*= 2) {
		two += n / i;
	}

	for (int i = 5; i <= n; i*= 5) {
		five += n / i;
	}

	if (five > two) {
		cout << two << "\n";
	}
	else {
		cout << five << "\n";
	}


	return 0;
}