백준 1676번: 팩토리얼 0의 개수 (C++)

백준 1676번 팩토리얼 0의 개수 (C++)

---

문제

N!에서 뒤에서부터 처음 0이 아닌 숫자가 나올 때까지 0의 개수를 구하시오. (0 ≤ N ≤ 500)

예를 들어

• 10! = 3,628,800 → 끝에 0이 2개 → 출력 2
• 3! = 6 → 끝에 0이 없음 → 출력 0

이 문제는 “팩토리얼 결과가 몇 개의 0으로 끝나는가”를 찾는 문제입니다.

문제풀이

● 0~20까지의 팩토리얼과 끝의 0 개수

N	N! 값 (일부 생략)	맨 끝의 0 개수
0	1	0
1	1	0
2	2	0
3	6	0
4	24	0
5	120	1
6	720	1
7	5,040	1
8	40,320	1
9	362,880	1
10	3,628,800	2
11	39,916,800	2
12	479,001,600	2
13	6,227,020,800	2
14	87,178,291,200	2
15	1,307,674,368,000	3
16	20,922,789,888,000	3
17	355,687,428,096,000	3
18	6,402,373,705,728,000	3
19	121,645,100,408,832,000	3
20	2,432,902,008,176,640,000	4

여기서 5!, 10!, 15!, 20!을 보면 0이 1, 2, 3, 4개씩 규칙적으로 늘어남을 알 수 있습니다.
즉, 어떤 특정 수를 곱할 때마다 0이 하나씩 추가된다는 뜻입니다.

● 0이 생기는 원인 — 10이 만들어질 때

곱셈의 끝에 0이 생기는 이유는 곱한 결과 안에서 10이 만들어졌기 때문입니다.
10은 2×5이므로, 결국 “2와 5가 한 쌍으로 만나면 0이 하나 생긴다”고 볼 수 있습니다.

● 그런데 2는 매우 많다

1부터 N까지의 수를 모두 곱할 때, 짝수(2의 배수)가 아주 많습니다.
즉, 2는 넘쳐납니다. 2는 부족할 일이 없습니다. 그렇기 때문에 0의 개수는 오로지 5가 몇 번 등장하느냐에 따라 결정됩니다.

● 규칙 발견 – “5가 등장할 때마다 0이 하나씩 늘어난다”

1부터 차례대로 살펴보면 다음과 같습니다.

수	5 포함 여부	누적 0 개수
1	×	0
2	×	0
3	×	0
4	×	0
5	✓ (5 한 번)	1
6	×	1
7	×	1
8	×	1
9	×	1
10	✓ (5 한 번)	2
11~14	×	2
15	✓ (5 한 번)	3
16~19	×	3
20	✓ (5 한 번)	4
21~24	×	4
25	✓ (5 두 번)	6

즉, 5의 배수마다 0이 하나씩 증가하고, 25처럼 5가 두 번 들어 있는 수에서는 0이 한 개 더 증가합니다.

● 왜 25는 두 개의 0을 만들까?

25 = 5×5 이기 때문입니다.
25 안에는 5가 두 번 들어 있으므로 25!에서는 5가 하나 더 추가됩니다.
125 = 5×5×5 이면 5가 세 번, 625 = 5×5×5×5이면 5가 네 번 들어 있는 식입니다.
따라서 단순히 5의 배수만 세면 부족합니다. 25, 125, 625… 같은 수까지 모두 세야 정확히 계산됩니다.

● 그래서 나누는 이유 — 5, 25, 125 등으로 나눔

팩토리얼에서 0의 개수를 구하는 공식은 다음과 같습니다. \[ 0의\ 개수 = \left\lfloor \frac{N}{5} \right\rfloor + \left\lfloor \frac{N}{25} \right\rfloor + \left\lfloor \frac{N}{125} \right\rfloor + \cdots \]

• N ÷ 5 : 5의 배수 개수 (5, 10, 15, 20, 25, …)
• N ÷ 25 : 25의 배수 개수 (25, 50, 75, 100, …)
• N ÷ 125 : 125의 배수 개수 (125, 250, 375, …)
• N ÷ 625 : 625의 배수 개수 (625, 1250, 1875, …)

나눈 값이 0이 될 때까지 계속 더합니다.
이렇게 하면 25처럼 5가 여러 번 들어 있는 수까지 모두 세어집니다.

● 예시로 실제 계산

N = 10

\[ \lfloor 10/5 \rfloor = 2,\ \lfloor 10/25 \rfloor = 0 \] → 총합 = 2 → 10!의 끝 0은 2개

N = 25

\[ \lfloor 25/5 \rfloor = 5,\ \lfloor 25/25 \rfloor = 1 \] → 총합 = 6 → 25!의 끝 0은 6개

N = 100

\[ \lfloor 100/5 \rfloor = 20,\ \lfloor 100/25 \rfloor = 4 \] → 총합 = 24 → 100!의 끝 0은 24개

● 이 방법이 효율적인 이유

단순히 팩토리얼을 계산하는 건 불가능합니다.
500!은 1,000자리가 넘는 수이기 때문입니다.
하지만 위의 방식은 단순히 정수 나눗셈 몇 번만 하면 되므로 시간복잡도는 O(log₅N)입니다.
즉, N=500이어도 매우 빠릅니다.

코드

  
#include 

using namespace std;
int main(void)
{
	int N,sumN=0,k=1;
	cin >> N;

	while (true)
	{
		k *= 5;
		
		
		
		sumN += N / k;
		if (N / k == 0)
			break;
		
		
	}

	cout << sumN << endl;
}

요약

구분	내용
핵심 개념	팩토리얼의 끝 0은 10(=2×5)이 만들어질 때마다 생김
2의 개수	항상 충분하므로 무시
5의 개수	5의 배수마다 0이 하나 증가
25, 125, 625…	5가 중복 포함되므로 추가로 더해야 함
계산식	N ÷ 5 + N ÷ 25 + N ÷ 125 + ... (몫이 0이 될 때까지)
예시	N=10 → 2개, N=25 → 6개, N=100 → 24개
시간복잡도	O(log₅N) (매우 빠름)

결론:
팩토리얼의 끝에 생기는 0의 개수는 1부터 N까지의 모든 수 안에 포함된 5의 개수를 전부 더한 값이며, 이를 계산하기 위해 5, 25, 125, 625로 계속 나누어 몫을 합산하면 됩니다.