[1676] 팩토리얼 0의 개수

---

소인수분해의 특징을 찾으라는데, 나는 규칙을 찾아서 풀었다

 

5의 배수일 때 0의 개수가 늘어나는데, 만약 25의 배수면 하나 더 증가, 125의 배수면 또 하나 증가가 되는 성질을 발견하였다

그래서 미리 크기 501의 배열을 만든 후 그 안에 0의 개수를 for문을 이용하여 할당해주었다

다시 보니 5의 x제곱일 때 k가 x씩 늘어나는 것 같다

하지만 크기가 500까지였으므로 굳이 정리하여 적진 않았다

 

그렇게 완성된 코드는 아래와 같다

#include <iostream>
using namespace std;

int A[501];
int N;

void f() {
	int k = 0;
	for (int i = 0; i <= 500; i++) {
		if (i % 5 == 0 && i!=0) { // 5, 10, 15, 20 ,,,
			if (i % 25 == 0) { // 25, 50, 75,,
				if (i % 125 == 0) { // 125, 250, 500
					k++;
				}
				k++;
			}
			k++;
		}
		A[i] = k;
	}
}

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

	f();
	cin >> N;

	printf("%d",A[N]);
}

 

---

문제를 풀고 난 후 다른 사람들의 풀이를 보았다

0의 개수를 구한다는 10의 개수를 구한다는 것과 마찬가지이다

그럼 2*5의 개수를 구해야된다는 건데, 2는 5보다 작아서 소인수분해 할 때 항상 5의 개수보다 많다

그러므로 조금 특이 케이스인 5의 개수를 세면 된다(정확히는 5의 배수의 개수)

5, 10, 15, 20에서는 1 증가한다

대신, 25, 50, 75에서 1씩 더 증가하고,

125, 250, 375, 500에서 1씩 더 증가한다

5의 x승마다 1이 더 증가한다는 규칙을 발견하였다