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

www.acmicpc.net/problem/1676

1676번: 팩토리얼 0의 개수

N!을 직접 구하는 것은 숫자가 기하급수적으로 커지므로 직접 구하면 아마 오버플로우가 날 것이다.

따라서 다른 방법을 사용했다.

어떤 숫자가 뒤에서부터 0이 1개 나온다는 것은 10의 배수라는 것이다.

어떤 숫자가 뒤에서부터 0이 연속으로 2개 나온다는 것은 100의 배수라는 것이다.

어떤 숫자가 뒤에서부터 0이 연속으로 3개 나온다는 것은 1000의 배수라는 것이다.

그러므로 소인수분해를 하여 2와 5의 개수를 세어주면 된다.

2가 6개, 5가 3개면 10을 3개 만들 수 있다.

2가 100개이더라도 5가 3개이면 10을 3개만 만들 수 있다.

2가 5개, 5가 100개여도 10을 5개 만들 수 있다.

N부터 N-1, N-2, N-3, ... , 2, 1까지 각각을 소인수분해를 하여 2의 개수를 twoCount에, 5의 개수를 fiveCount에 저장하고 twoCount와 fiveCount 중에 더 작은 값이 10을 몇 개 만들 수 있는지를 뜻하므로 min(twoCount, fiveCount)를 출력하도록 했다.

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

int main() {
	int n;
	cin >> n;
	int twoCount = 0;
	int fiveCount = 0;
	for (int i = 1; i <= n; i++) {
		int num = i;
		while (num % 2 == 0) {
			num /= 2;
			twoCount++;
		}
		while (num % 5 == 0) {
			num /= 5;
			fiveCount++;
		}
	}
	cout << min(twoCount, fiveCount);
	return 0;
}