[백준] 알고리즘 C++ 1676번 - 팩토리얼 0의 개수문제

문제

https://www.acmicpc.net/problem/1676

1676번: 팩토리얼 0의 개수

소스코드

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

int main() {
	ios_base::sync_with_stdio(false), cin.tie(NULL); 
	int n, count = 0;
	cin >> n;
	for (int i = 2; i <= n; i++) {
		if (i % 5 == 0) count++;
		if (i % 25 == 0) count++;
		if (i % 125 == 0) count++;
	}
	cout << count;
}

해설

long long num = fact(n);
	for (int i = 2; i <= n; i++) {
		while (num % i == 0) {
			if (i == 5) count++;
			num /= i;
		}
	}

팩토리얼 계산된 num을 가지고 소인수분해를 진행하게 되면 시간초과가 나게된다.

우리는 좀 더 효율적인 계산 방법을 찾아내야한다.

2, 5를 곱하여 10을 만들면 끝자리 수가 0으로 되게됩니다.

5가 2보다 나올 개수가 더 작기때문에 5만 구해서 갯수를 출력해주면 된다.

 

굳이 팩토리얼을 계산하지 않고도

100! = 1 2 3 4 5 6 7 8 9 10 11 12 13 * * * 100  100까지의 숫자중 5의 제곱수마다 5가 들어가져있습니다.

그렇다면 2부터 n까지 숫자들중 5가 들어있나 확인하면됩니다.

결국 이말이 n! 에서 5를 찾는 것과 같습니다.

 

5의 제곱수를 주의해야하는데요

5 25 125

25는 5가 2개들어가있고

125는 5가 3개들어가있습니다.

 

즉 n은 500아래까지 나올 수 있는 5의 제곱수 최대값인 125까지 생각만 해주면됩니다.