문제

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

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

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

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

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

입력

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

출력

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

예제 입력

6
3
60
100
1024
23456
8735373

예제 출력

0
14
24
253
5861
2183837

내가 했던 풀이

0의 개수를 찾기 위해서는 소인수분해의 원리를 이용해 2와 5의 개수를 구하면 된다. 즉, 2와 5의 개수 중 더 작은 값이 0의 개수가 된다. 하지만 항상 2의 개수가 5의 개수보다 많으므로, 5의 개수만 구해주면 된다.

여기에 추가적으로 팩토리얼을 계산하지 않고도 5의 개수를 구할 수가 있다.

n!에서 5의 배수마다 5가 한 번씩 곱해진다. 또 25의 배수마다 5가 추가로 한 번 더 곱해집니다 (25 = 5×5). 또 125의 배수마다 5가 또 추가로 한 번 더 곱해집니다 (125 = 5×5×5). 이를 통해 알 수 있는 점은 입력받은 N에 5의 제곱수를 나눠주었을 때의 몫의 합이 구하려는 5의 개수가 되는 것이다. 그러므로 5에서 시작하여 num까지 5를 계속 곱해준 값을 num에 나눠준 뒤, 정수 부분을 더해주면 된다.

코드

const fs = require('fs');
let [T, ...N] = fs.readFileSync(0, 'utf-8').toString().trim().split('\n').map(Number);

function countZerosInFactorial(num) {
  let count = 0;
  for (let i = 5; i <= num; i *= 5) {
    count += Math.floor(num / i);
  }
  return count;
}

let answer = '';
for (let i = 0; i < T; i++) {
  answer += countZerosInFactorial(N[i]) + '\n';
}

console.log(answer.trim());

회고

이런 생각을 도대체 어떻게 하지...................... 한~참 정독해서 겨우 이해했다.