백준 / 수학 / 1676번 / 팩토리얼 0의 개수 / C++

문제

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

입력

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

출력

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

예제 입력 1

10

예제 출력 1

2

예제 입력 2

3

예제 출력 2

0

 

#include <iostream>
using namespace std;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	
	int n;
	cin >> n;
	
	int result = 0;
	
	for(int i=5; i<=n; i*=5) {
		result += n / i;
	}
	
	cout << result << '\n';

	return 0;
}

---

흔한 팩토리얼 구하는 알고리즘인 재귀나 반복문으로 하면 시간초과가 뜬다.

필자도 처음에 그렇게해서 시간초과가 떴다.

 

그래서 다른 방법을 찾아냈다.

보통 숫자의 0의 개수는 10의 배수가 몇번이냐에 따라서 0의 개수가 결정된다.

예를 들어 1000은 10 * 10 * 10 이고, 10이 3번곱해져서 0의 개수가 3개이다.

그래서 10의 배수가 몇번이 나오나 생각해보면된다.

 

일단 n이 10일때를 가정해보자.

그러면 10! = 10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1 일것이다.

10 = 2 * 5 이므로 2 * 5의 갯수를 세면 되는데, 

10 = 2 * 5
9 = 3 * 3
8 = 2 * 2 * 2
7 = 7
6 = 2 * 3
5 = 5
4 = 2 * 2
3 = 3
2 = 2
1 = 1

이므로 총 2의 갯수는 8개, 5의 갯수는 2개 이므로 만들어질 수 있는 2 * 5의 쌍의 갯수는 2개이다.

따라서 10의 갯수는 5의 갯수와 같다. (5가 나오기 전에 2가 무조건 나올 수 밖에 없다.)

 

따라서 어떤 숫자 num이라는 변수가 있다고 하면, num은 몇개의 5로 이루어져 있는지 알려면(소인수분해)

단순히 5로 나누어 보면된다.

10까지의 수중에서 5는 5와 2*5인 10이 5를 1개씩 가지고있다.

그리고 5의 갯수가 10의 갯수와 같으므로, 5의 갯수가 2개일때는 5*5인 25부터 일것이다.

따라서 우리는 25전까지의 수(<=24)는 5가 무조건 한개일수밖에 없다는 것을 알 수 있다.

 

그래서 모든 수를 비교할 필요는 없고, 5가 1개일때, 5가 2개일때, 5가 3개일때.... 즉 5, 25, 125 일때 

n을 5, 25, 125로 나눠주며 갯수를 카운팅하면된다.