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

문제

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

입력

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

출력

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

---

N의 팩토리얼을 구했을 때 0이 몇개가 연속으로 나오는지 구하는 문제이다.

0의 개수를 구하기 위해선 N의 팩토리얼에 10이 몇 번 곱해지는지를 알면 된다.

그렇다면 일일이 10으로 나눠 나머지가 0이 되는 개수를 구하면 될 줄 알았지만 아니다.

10은 2와 5의 곱이기 때문이다. 

팩토리얼을 구하는 과정에서 2는 충분히 많은 수가 곱해질 것이므로 5가 몇개나 곱해져있는지를 구하면 문제를 해결할 수 있다. 

1부터 N까지 for문을 돌리며 5의 배수가 몇 번이나 나오나 세서 출력해주자.

 

 

코드 원본 : https://github.com/chosh95/STUDY/blob/master/BaekJoon/2020/%ED%8C%A9%ED%86%A0%EB%A6%AC%EC%96%BC%200%EC%9D%98%20%EA%B0%9C%EC%88%98(1676%EB%B2%88).cpp

chosh95/STUDY

C++ 코드

#include <iostream>
using namespace std;
int N, res;

void fact()
{
	res = 0;
	for (int i = 2; i <= N; i++) {
		int tmp = i;
		while (tmp % 5 ==0) {
			res++;	
			tmp /= 5;
		}
	}
}

int main()
{
	cin >> N;
	fact();
	cout << res;
}