[백준 3474] 교수가된 현우

문제

알고리즘의 킹갓제너럴엠퍼러마제스티충무공알고리즘마스터 현우가 교수로 취임하였다!

그러나 학생들에게 크나큰 기대를 품고 첫 수업에 들어갔던 현우는 아무도 외판원 순회 문제(Traveling Salesman Problem, TSP)를 풀지 못하는 것을 보고 낙심하였다.

그 와중에 학생 남규는 TSP를 완전탐색으로 풀려고 하였고, 현우는 그걸 보고 경악을 금치 못한다. 왜냐면 TSP를 완전탐색으로 풀려면 O(N!)의 시간이 소모되는데, 이는 경악을 금치 못할 시간이기 때문이다.

그러나 남규는 O(N!)이 왜 큰지도 잘 모른다. 그래서 현우는 더더욱 경악을 금치 못하고, N!이 얼마나 큰지 대략적으로나마 알려주기 위해, 자연수 N이 주어지면 N!의 오른쪽 끝에 있는 0의 개수를 알려주기로 하였다.

그러나 현우는 경악을 금치 못하여 지금 코딩을 할 수 없는 상황이다. 여러분이 현우를 대신하여 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어지고, 이어서 T개의 줄에 정수 N이 주어진다(1 <= N <= 1000000000).

출력

각 줄마다 N!의 오른쪽 끝에 있는 0의 개수를 출력한다.

설계 및 코드

0의 개수를 세는 문제입니다. 2300의 0의 개수는 23 * 100 -> 100 = 10 * 10 입니다. 결국 10의 개수가 몇개인가에 따라 맨 뒤 0의 자릿수를 결정합니다. 10은 2 * 5로 만들 수 있습니다.(10 * 1도 가능하지만 그냥 10이기 때문에 의미가 없습니다.) 그럼 이제 2와 5의 개수를 세면 어떤 팩토리얼이 와도 0의 개수를 셀 수 있습니다. 

이렇게 2의 제곱을 통해 2의 개수를 셀 수 있습니다. 2와 5의 경우를 두가지를 나눠 탑색을 합니다. 8!이면 2부터 시작해서 8까지 2의 배수들로 나눠 2의 개수를 모두 구하고 5부터 시작해서 8까지 5의 배수들로 나눠 5의 개수를 구합니다. 이렇게 n! 내부의 2와 5의 개수를 구하고 두개의 조합이 있어야 10이 되기 때문에 둘다 있을 수 있는 둘 중 가장 작은 개수를 반환하면됩니다.

#include<bits/stdc++.h>
using namespace std;
int n,a;

int main(){
    ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
    cin >> n;
    for (int i = 0; i < n; i++){
        cin >> a; // 16
        int ret2 = 0 , ret5 =0;

        for (int j = 2; j <= a; j *= 2){
            ret2 += a/j; // 2, 4, 8, 16 
        }

        for(int j = 5; j <= a; j *= 5){
            ret5 += a/j;
        }

        cout << min(ret2,ret5) << "\n";
    }
    return 0;
}