팩토리얼 0의 개수 (feat. 백준, 1676번)

팩토리얼 0의 개수
https://www.acmicpc.net/problem/1676

1676번: 팩토리얼 0의 개수

반응형

// woohyeon.kim
// https://www.acmicpc.net/problem/1676
#include <iostream>
#include <cmath>
using namespace std;
int main() {
	ios::sync_with_stdio(false), cin.tie(NULL);
	register int N, ans = 0, idx = 0, tmp;
	cin >> N;
	while (true) {
		tmp = pow(5, ++idx);
		if (tmp > 500)
			break;
		ans += N / tmp;
	}
	cout << ans;
	return 0;
}
// *&)*@*

• 팩토리얼의 값은 500 이하입니다. 30! 이 넘어가기 시작하면 64비트 정수형으로도 담을 수 없기 때문에 실제 팩토리얼을 구하는 문제는 아닙니다. (시간 제한을 봐도 불가능합니다.)
• 따라서 0부터 10 팩토리얼의 값을 구해봅니다.

• 5 ~ 9 팩토리얼은 우측부터 0이 아닐때 까지의 0의 개수는 1개 입니다.
• 10 팩토리얼은 우측부터 0이 아닐때 까지의 0의 개수는 2개 입니다.
• 따라서 N! 중 N을 5로 나눈 값이 0의 개수가 됩니다.
• 하지만 이렇게 하면 오답이 됩니다. 왜일까요? 20! ~ 30!을 구해보겠습니다.

• 24! 까지는 24 / 5 = 4 개의 0이 나오지만 25부터는 6개가 나오게 됩니다.
• 즉 N! 중 N을 5로 나눈 값 + N을 25로 나눈 값 + N을 125로 나눈 값 + ... 이 답이 되게 됩니다.
• 문제에서 N은 500까지 이므로 500이 되기 전의 5의 제곱승은 125가 최대입니다.
• 따라서 N/5 + N/25 + N/125 가 점화식으로 도출됩니다.