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

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

1676번: 팩토리얼 0의 개수

 

 N 팩토리얼 문제는 보통 재귀 호출을 통해 풀 수 있습니다. 때문에, 처음 문제를 접했을 때 재귀 호출을 통해 N! 을 먼저 구한 뒤에 답을 도출했습니다. 

 

 하지만! 이 방법으로 문제를 풀게 되면 시간초과가 뜹니다 ㅠ ㅠ 팩토리얼을 구하는 데에 너무 많은 시간을 소비하기 때문이지요.

 

 처음 0이 아닌 숫자가 나올때까지의 0의 개수를 구하라는 것은 즉 10의 개수, 더 정확히 말하자면 5의 개수를 구하라는 것입니다!

 

 예시로 100!을 보겠습니다. 5의 배수를 제외한 나머지 숫자들은 약수로 5를 가지지 않기 때문에 5의 배수만 놓고 보겠습니다. 

 

5	10	15	20	25
30	35	40	45	50
55	60	65	70	75
80	85	90	95	100

 

 5의 배수들이기 때문에 5가 적어도 1개는 포함되어 있습니다. 

 

 5의 제곱인 25의 배수들은 5가 2개 포함되어 있지요.

 

 그렇다면, 5의 세제곱인 125의 배수들은 5가 3개 포함되어 있습니다. 

 

 자 이제 패턴을 알았으니 100! 안에 5가 대체 몇 개 포함되어 있느냐?

 

 5의 배수들은 +1, 25(5^2)의 배수들은 +2, ...

 

 먼저 100 이하 숫자 중 5의 배수인 숫자들의 개수는 100 / 5 = 20 개입니다.

 

 다음으로 100 이하 숫자 중 25의 배수인 숫자들의 개수는 100 / 25 = 4 개입니다. 

 

 그렇다면 N! 안의 5의 개수는 다음 수식으로 나타낼 수 있습니다. 

 

5	10	15	20	25	30	35	40	45	50	55	60	65	70	75	80	85	90	95	100
+1	+1	+1	+1	+1	+1	+1	+1	+1	+1	+1	+1	+1	+1	+1	+1	+1	+1	+1	+1
				+1					+1					+1					+1

 

 코드는 다음과 같습니다.

 

#include<iostream>

using namespace std;

int main(void) {

	cin.tie(NULL);
	cout.tie(NULL);
	ios_base::sync_with_stdio(false);

	int n;
	int ans = 0;

	cin >> n;

	if (n < 5) {
		ans = 0;
	}
	else {

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

	cout << ans << endl;

	return 0;
}