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

https://www.acmicpc.net/problem/1676

1676번: 팩토리얼 0의 개수

문제

---

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

 

입력

---

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

 

출력

---

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

 

문제 풀이

---

수학을 이용한 문제.

0의 개수를 구하는 것은 결국 10이 몇 번 등장하는지를 구하는 문제이다. 10이 나올 수 있는 경우는 10의 배수이거나, 2*5를 이용하는 방법이 있다.

2*5를 이용한다면 10이 나올 수 있는 개수는 2와 5중 개수가 더 적은 쪽을 따르게 되는데, 팩토리얼은 1부터 N까지 수가 한번씩 나오고, 따라서 5의 개수에 영향을 받는다. 즉, N까지의 숫자중 5의 배수가 있다면 그 이전의 2와 곱해져 10의 개수가 1 늘어난다. N까지의 숫자 중 25의 배수가 있다면 5가 2개가 되고, 그 이전의 2 2개와 곱해져 10을 두 개 만들 수 있다. 같은 방식으로 125의 배수는 10을 3개 만들 수 있고, 625의 배수는 10을 4개 만들 수 있다.

10의 배수는 5의 배수이므로 5의 배수 경우에 포함된다.

 

아래는 코드.

#include <iostream>
using namespace std;

int main()
{
	int N;
	int count = 0;
	cin >> N;
	for (int i = 1; i <= N; i++)
	{
		if (i % 125 == 0)
		{
			count += 3;
		}
		else if (i % 25 == 0)
		{
			count += 2;
		}
		else if (i % 5==0)
		{
			count++;
		}
	}
	cout << count << "\n";
	return 0;
}