백준 2004 조합 0의 개수 (수학)

문제

풀이

let input = require('fs').readFileSync('/dev/stdin').toString().trim();
const calc = (n) => {
  let num = n;
  let twoCount = 0;
  let fiveCount = 0;

  for (let i = 2; i <= num; i *= 2) {
    twoCount += parseInt(num / i);
  }

  for (let i = 5; i <= num; i *= 5) {
    fiveCount += parseInt(num / i);
  }

  return [twoCount, fiveCount];
};

const sol = (input) => {
  const [n, m] = input.split(" ").map(Number);
  const nm = n - m;

  const two = calc(n)[0] - (calc(m)[0] + calc(nm)[0]);
  const five = calc(n)[1] - (calc(m)[1] + calc(nm)[1]);

  return Math.min(two, five);
};

console.log(sol(input));

• 조합 계산식 : n! / (n-m)! * m!
• n!, (n-m)!, m!이 가지고 있는 2와 5의 개수를 각자 구하여 n!의 2의 개수에서 (n-m)!와 m!의 2의 개수를 합친 값을 뺀다. 5의 경우에도 동일한 방법으로 계산한다. 그냥 식이다.
• 2의 개수, 5의 개수를 구하는 것은 앞 문제 0의 개수를 구하는 방법과 동일하다.