[Baekjoon/C++] 1676번 - 팩토리얼 0의 개수

[백준] Baekjoon Online Judge

문제로 이동

 

문제

N!에서 뒤에서부터 처음 0이 아닌 숫자가 나올 때까지 0의 개수를 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에 N이 주어진다. (0 ≤ N ≤ 500)

 

출력

첫째 줄에 구한 0의 개수를 출력한다.

 

---

예제 입력	예제 출력
10	2
3	0

---

풀이

#include <iostream>
using namespace std;

int main() {
	int N;
	scanf("%d", &N);

	int count = 0; // 0의 개수
	
	for (int i = 5; i <= N; i *= 5)
		count += (N / i);

	// 0의 개수를 출력
	printf("%d\n", count);

	return 0;
}

입력 받은 N의 팩토리얼 결과의 0의 개수는 N을 5의 배수로 나눈 수의 합과 같다.

N!의 0은 N!이 10으로 몇번 나눌 수 있는지에 따라 개수가 달라지는데, 10의 약수는 2와 5이다. 2의 배수는 대부분 5보다 많으므로 N! 속의 5의 수만 알면 된다.

 

	1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
5	        1          2              3              4              5
25                                                                  1		총 : 5 + 1 = 6개

N을 5의 배수로 나누면 위와 같은 결과가 나온다. 25의 경우 5 * 5로 5가 2번 들어가기에 두 번 세야하고 125의 경우는 3번 세야한다. 이런 경우는 5의 배수 25, 125, ...로 나눈 결과가 해결해준다.