문제 설명

---

백준 3474는 어떤 수 N이 주어졌을 때 N!에서 우측에 0이 몇 개 있는 지 갯수를 세는 문제이다.
N의 범위가 1 ~ 1,000,000,000이기 떄문에 일반적인 계산으로 0을 구하는 것은 불가능하다.

풀이 전략

---

문제 분석

1. 우측에 0을 갖는 어떤 수 K가 있다고 가정해 보자. 이때 K는 아래와 같이 표현할 수 있다.

   K = M * 10^N (M은 우측의 0이 끝난 지점부터의 수)
   ex) 5891000 = 5891 * 10^3

2. 10은 2와 5를 인수로 갖는다.(10 = 2 * 5) 즉, 어떤수를 구성하는 2 * 5의 쌍이 몇개인지가 해당 수의 0의 갯수를 결정한다.
   일반적으로 소인수분해의 결과로는 2와 5의 지수 중 2보다 5의 지수가 더 낮음으로 5의 지수를 구해주는 방향으로 코드를 작성하면 0의 갯수를 구할 수 있다.

   ex) K = 5! = 120
   5! = 1 * 2 * 3 * 4 * 5
   = 2^3 * 3 * 5
   
   ex) K = 10! = 3628800
   10! = 1 * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 * 10
   = 2^8 * 3^4 * 5^2 * 7

3. K!에 대하여 k에 5^n이 몇 개씩 들어있는 지 총 합을 구해준다.

   ex) K = 60!
   60! = 1 * 2 * 3 ... 58 * 59 * 60
   60 / 5^1 = 12
   60 / 5^2 = 2
   
   ex) K = 1024!
   1024!= 1 * 2 * 3 ... 1022 * 1023 * 1024
   1024 / 5^1 = 204
   1024 / 5^2 = 40
   1024 / 5^3 = 8
   1024 / 5^4 = 1

풀이 코드

---

import java.io.*;
import java.util.*;

public class PN3474 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        
        int n = Integer.parseInt(br.readLine());
        
        for(int i = 0; i < n; i++) {
            int input = Integer.parseInt(br.readLine());
            int result = 0;
            
            for(int j = 5; j <= input; j += 5) {
                result = input / j;
            }

            sb.append(result).append('\n');
        }

        System.out.print(sb);
    }
}