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

문제 링크: https://www.acmicpc.net/problem/1676

 

\(N!\)에서 뒤에서부터 처음 0이 아닌 숫자가 나올 때까지 0의 개수를 구하는 문제입니다.

뒤에서부터 0의 개수를 센 뒤 +1 해서 출력하면 됩니다.

0의 개수는 어떻게 셀까요? \(N\)의 최대값이 500이기 때문에 \(N!\)을 직접 구하는 건 무리가 있겠죠. 

 

500! =
1220136825991110068701238785423046926253574342803192842192413588385845373153881997605496
4475022032818630136164771482035841633787220781772004807852051593292854779075719393306037
7296085908627042917454788242491272634430567017327076946106280231045264421887878946575477
7149863494367781037644274033827365397471386477878495438489595537537990423241061271326984
3277457155463099772027810145610811883737095310163563244329870295638966289116589747695720
8792692887128178007026517450776841071962439039432253642260523494585012991857150124870696
1568141625359056693423813008856249246891564126775654481886506593847951775360894005745238
9403357984763639449053130623237490664450488246650759467358620746379251842004593696929810
2226397195259719094521782333175693458150855233282076282002340262690789834245171200620771
4640979456116127629145951237229913340169552363850942885592018727433795173014586357570828
3557801587354327688886801203998823847021514676054454076635359841744304801289383138968816
3948746965881750450692636533817505547812864000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000000000000000000

팩토리얼 구하는 사이트로 확인하니 500!이 이렇게 큽니다.

 

뒤에 0이 나오는 경우는 10이 곱해진 경우밖에 없습니다. \(10 = 2 \times 5\)이므로 \(N!\)을 소인수분해 했을 때 나오는 2와 5의 개수를 세서 \(min(2의 개수, 5의 개수)\)를 구하면 됩니다.

그런데 생각해보면 5의 개수가 항상 2의 개수보다 적기 때문에 5의 개수만 세면 됩니다.

5의 개수는 어떻게 셀까요?

 

\begin{array} {|r|r|}
\hline 1 & 2 & 3 & 4 & \color{blue}5 & 6 & 7 & 8 & 9 & \color{blue}10 \\
\hline 11 & 12 & 13 & 14 & \color{blue}15 & 16 & 17 & 18 & 19 & \color{blue}20 \\
\hline 21 & 22 & 23 & 24 & \color{red}25 & 26 & 27 & 28 & 29 & \color{blue}30 \\
\hline 31 & 32 & 33 & 34 & \color{blue}35 & 36 & 37 & 38 & 39 & \color{blue}40 \\
\hline 41 & 42 & 43 & 44 & \color{blue}45 & 46 & 47 & 48 & 49 & \color{red}50 \\
\hline 51 & 52 & 53 & 54 & \color{blue}55 & 56 & 57 & 58 & 59 & \color{blue}60 \\
\hline 61 & 62 & 63 & 64 & \color{blue}65 & 66 & 67 & 68 & 69 & \color{blue}70 \\
\hline 71 & 72 & 73 & 74 & \color{red}75 & 76 & 77 & 78 & 79 & \color{blue}80 \\
\hline 81 & 82 & 83 & 84 & \color{blue}85 & 86 & 87 & 88 & 89 & \color{blue}90 \\
\hline 91 & 92 & 93 & 94 & \color{blue}95 & 96 & 97 & 98 & 99 & \color{red}100 \\
\hline \end{array}

100!의 0의 개수를 계산한다고 생각해봅시다.

위 표에서 파란색 글씨가 5의 배수이고, 그 중 25의 배수는 빨간색으로 표시했습니다.

1에서 100까지 인수가 5로 들어가는 것을 발견하면 +1, 인수가 5*5인 것은 +2, 이런식으로 더하면 5의 개수를 셀 수 있습니다. 식으로 표현하면 아래와 같습니다.

\[ \left \lfloor \frac{N}{5} \right \rfloor + \left \lfloor \frac{N}{5^2} \right \rfloor + \left \lfloor \frac{N}{5^3} \right \rfloor \cdots \]

 

#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>

using namespace std;

int main()
{
#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
#endif

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

	int n;
	int ans = 0;
	cin >> n;

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

	return 0;
}

소스입니다.