[boj] 2004. 조합 0의 개수 (node.js)

문제

[boj] 2004. 조합 0의 개수 (node.js)

풀이

• 조합은 팩토리얼로 바꿀 수 있고, 팩토리얼에서의 인수의 개수를 확인하는 문제로 바꿔 생각할 수 있다.

• 뒤에서부터 0의 개수는, 10 = 2 * 5 이므로 2의 인수의 개수와 5의 인수의 개수 중 더 작은 수와 같다.

  • 추후 서치하다 알게 된 점: 5의 인수의 개수는 반드시 2의 인수의 개수보다 작을 수밖에 없다. (두 수 2, 5가 모두 소수이기 때문에 성립) 따라서 5의 인수의 개수만 구하면 된다.

• 따라서, 이 문제를 풀기 위해서는 팩토리얼에서 인수의 개수를 구하기 위하는 호율적인 방법을 알면 된다.

• 팩토리얼에서 인수의 개수는,

  • ex) n!에서 k의 인수의 개수를 구하는 법
    • -> (n/k**1) + (n / (k ** 2)) + (n/(k ** 3)) + ... + (n/k**i)
    • n을 k의 1승부터 n승까지, k ** i가 n보다 작거나 같을 때까지 더해주면 된다.
  • 단, 이 방법을 적용할 때는 항상 n!을 (n부터 1까지 연속적으로) 모두 곱하는 경우여아 한다.
  • 해당하는 인수를 1승만큼 추가로 가질 때마다 +1 되어 총 개수가 더해자는 원리이므로 (n n-1 ... * 5) 이렇게 멈추는 경우는 잘못된 결과값이 된다.

생각

• 초반에 여러 방법으로 접근해 봤다. 유사한 문제를 풀었을 때처럼 조합을 구해서 결과값으로 0의 개수를 알아내려고도 했고, 제곱수를 하나씩 완전탐색하려고도 했다.
• 하지만 n, m이 최대 1000000000 (0이 9개) 이므로 이 방법들은 시간초과가 발생한다.
• 따라서, 적어도 자바스크립트로 시간 내에 풀이하기 위해서는 반드시 위에서 설명한 인수의 개수를 구하는 방법을 알고 있어야 한다. 짚고 넘어가야만 하는 요긴한 문제를 풀이한 것 같아 좋다!

전체 풀이

const readline = require("readline");
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

const solution = () => {
  const [n, m] = input().split(" ");
  let results = [0, 0];
  numCounter(n);
  numCounter(n - m, -1);
  numCounter(m, -1);
  console.log(Math.min(...results));

  function numCounter(target, mul = 1) {
    let cnt = [0n, 0n];
    [2n, 5n].forEach((elem, index) => {
      for (let i = elem; i <= BigInt(target); i *= elem) {
        cnt[index] += BigInt(target) / i;
      }
    });
    cnt.forEach((elem, idx) => (results[idx] += mul * elem.toString()));
  }
};

let line = 0;
const input = () => stdin[line++];

let stdin = [];
rl.on("line", function (line) {
  stdin.push(line);
}).on("close", function () {
  solution();
  process.exit();
});