팩토리얼 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 two(register int n) {
	register int value = 0;
	for (register int i = 2; i <= n; i *= 2)
		value += n / i;
	return value;
}
int five(register int n) {
	register int value = 0;
	for (register int i = 5; i <= n; i *= 5)
		value += n / i;
	return value;
}
int main() {
	ios::sync_with_stdio(false), cin.tie(NULL);
	register int N;
	cin >> N;
	cout << min(five(N), two(N));
	return 0;
}
// *&)*@*

기존의 문제풀이와 다른 방식으로 풀어보았습니다.

아래와 같이 푸는 방법도 있으니 참고하시기 바랍니다.

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

---

문제에서처럼 우측이 0이 나오기 위해서는 10으로 나누어 떨어져야 합니다.

10은 2로 나누어 떨어지고 5로도 나누어 떨어져야 합니다.

 

0! ~ 10!의 값을 구해보겠습니다.

• 5는 5로 나누어지고 1입니다. 5는 2로 나누어지고 2입니다. 1과 2중 최소값은 1 입니다.
• 10은 5로 나누어지고 2입니다. 10은 2로 나누어지고 5입니다. 2와 5중 최소값은 2 입니다.
• 따라서 min(5로 나눈 몫, 2로 나눈 몫) 일 것 같지만 이렇게 되면 오답입니다.
• 왜일까요

20! ~ 29!의 값을 구해보겠습니다.

• 20은 5로 나누어지고 4입니다. 20은 2로 나누어지고 10입니다. 4와 10중 최소값은 4 입니다.
• 25는 5로 나누어지고 5입니다. 25는 2로 나누어지고 12입니다. 5와 12중 최소값은 5 입니다.
• 하지만 25!는 6개의 0을 갖습니다.
• 왜일까요

20! ~ 29!의 결과에 의하면 0! ~ 10!에서 도출된 식은 틀렸습니다.

• 위 빨간색 글씨를 자세히 보겠습니다. 25는 5로 나누어지고 5입니다. 또한 5^2인 25로도 나누어지고 1입니다. 따라서 25는 5로도 나누어지고 25로도 나누어지며 5 + 1 = 6 입니다.
• 25는 2로 나누어지고 12입니다. 또한 2^2, 2^3, 2^4로도 나누어집니다. 하지만 2^5 = 32 보다는 작은 값이므로 비교대상이 아닙니다.
• 따라서 N!은 (N/5 + N/25 + N/(5^X가 N보다 작거나 같을때까지)), (N/2 + N/4 + N/(2^X가 N보다 작거나 같을때까지)) 중 작은 값이 바로 0의 개수가 됩니다.