[백준/node.js] - 1676번 - 팩토리얼 0의 개수

문제

백준 1676번

풀이

문제에서 원하는 값은 뒷자리의 0의 갯수만 구하면 되므로 2의 배수와 5의 배수를 모두 세면 되는데 그 중 적은 갯수만큼 0이 붙는다.
2의 배수는 짝수이므로 5의 배수보다 무조건 갯수가 많다. 그러므로 5의 배수의 갯수만 세면 된다.

그 중에서도 25 는 5x5로 5를 2번 사용하는데 앞에 충분히 많은 2의 배수가 있기 때문에 2x5 가 2번 발생하는 것과 같다.
즉, 25의 배수는 0이 2개 붙는다는 말이다.
정리하자면 0이 붙는 경우는 5의 배수는 1개, 25(5x5)의 배수는 2개, 125(5x5x5)의 배수는 3개가 된다.
이때 문제에서 N이 500보다 작거나 같다고 했으므로 125까지만 해당한다.

let fs = require('fs');
let input = fs.readFileSync('/dev/stdin').toString().split(' ');


function Factorial(input) {
  let answer = 0
  if(input === 0) answer
  for(let i = 1; i <= input; i++){
    
    if(i % 5 === 0) answer++
    if(i % 25 === 0) answer++
  	if(i % 125 === 0) answer++
  }
  return answer
}

console.log(Factorial(input))

처음에는 팩토리얼 함수를 구현해야하는 줄 알고 빙빙 돌아갔는데 알고보니 팩토리얼 함수를 직접 구현할 필요가 없고 패턴을 찾는 문제였다. 알고리즘은 역시 너무 어렵다....

Ref

참고 블로그