[백준 c++] 3474 교수가 된 현우

문제 설명

https://www.acmicpc.net/problem/3474
입력으로 테스트 케이스 개수 T, 이어서 T개의 줄에 정수 N이 주어진다.
각 줄마다 N!의 오른쪽 끝에 있는 0의 개수를 출력하는 문제다.

아이디어

팩토리얼 결과의 오른쪽 끝에 0은 결국 10으로 이루어지는데 10은 2와 5로 이루어지기 때문에 N!의 2와 5의 개수를 찾는다.

정수 N의 범위가 1 <= N <= 1000000000인데 N!를 계산하면 수가 너무 커져서 이 숫자 그대로는 계산할 수 없다. 💨나열해서 규칙 찾자

예를 들어서 10!일 때는 2가 10/2 + 10/4 + 10/8 = 8 번 들어간다.
5도 이런식으로 구해서 2와 5중에 더 적게 들어간 개수를 출력해주면 된다.

전체 코드

#include<iostream>
#include<algorithm>
using namespace std;
int t,n;

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	cin >> t;
	while (t--) {
		int tcnt = 0, fcnt=0;
		cin >> n;
		int tpow = 2;
		int fpow = 5;
		while (tpow <= n && fpow <= n) {
			tcnt += n / tpow;
			tpow *= 2;
			fcnt += n / fpow;
			fpow *= 5;
		}
		cout << min(tcnt, fcnt) << '\n';
	}
}