3474 교수가 된 현우

실제 N!을 구하는 문제가 아닌, 뒤에 0이 붙는다는 것은 10으로 나누어 떨어진다는 것이다. 0의 갯수는 결국 10으로 몇번 나누어 떨어지는지를 의미하고, 10은 2와 5의 곱이므로 2와 5의 갯수를 구하면 된다

 

예를 들어 N=40이라면, 1~40까지 처음 2로 떨어지는 수는 N/2인 20개다. 다음 2*2인 4로 떨어지는 수는 N/4=10개다. 따라서 이렇게 나올 수 있는 2의 갯수와 마찬가지로 5의 갯수도 구할 수 있다

 

문제: https://www.acmicpc.net/problem/3474

깃허브주소: https://github.com/surinoel/boj/blob/master/3474.cpp

 

	#include <iostream>
	#include <algorithm>
	using namespace std;
	typedef unsigned long long ull;
	int main(void) {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	int tc;
	cin >> tc;
	while (tc--) {
	ull n;
	cin >> n;
	ull cnt2 = 0, cnt5 = 0;
	for (ull i = 2; i <= n; i *= 2) {
	cnt2 += n / i;
	}
	for (ull i = 5; i <= n; i *= 5) {
	cnt5 += n / i;
	}
	cout << min(cnt2, cnt5) << '\n';
	}
	return 0;
	}

view raw 3474.cpp hosted with ❤ by GitHub