백준 1676 : 팩토리얼 0의 개수

★★★☆☆

알고나면 간단하지만 풀때는 생각안나는 문제..

<나의 풀이>

#include <iostream>
using namespace std;
int main() {
	int n;
	cin >> n;

	int ret = 0;
	ret = n / 5 + n / 25 + n / 125;

	cout << ret << "\n";
	
	return 0;
}

직접 팩토리얼을 구해보니 20! 이상으로는 overflow가 발생했다.
그렇다면 숫자를 분해해보아야한다는 생각이 들었다.
단순하게 10,2,5의 경우만 생각했는데 5의 제곱수에 해당하는 숫자들이 영향을 끼친다는 것을 알았다.

/
주어지는 n은 500이하이므로 직접 5와 25, 125로 나눈 값들을 더해주었지만,
n이 그것보다 더 큰 범위라면 반복문을 사용해서 풀 수 있을 것이다.
/

코드는 간단하지만 알고리즘 자체는 간단하지 않았다..

https://huiung.tistory.com/82

<다른 사람의 풀이>

직접 곱해지는 수를 소인수분해하고, 그 때의 2와 5의 개수를 카운트한다.
최종적으로 두 수들 중 작은 값의 개수를 출력한다.

https://hoho325.tistory.com/245