[Baekjoon] 2004 조합 0의 개수(자바스크립트/NodeJs)

이번 문제는 아래 링크에서 풀어볼 수 있습니다.

2004번: 조합 0의 개수

---

문제

입력

출력

예제 입력 1

25 12

예제 출력 1

2

---

정답 코드

답안

const fs = require('fs');
const filePath = process.platform === 'linux' ? '/dev/stdin' : './input.txt';
let input = fs
    .readFileSync(filePath)
    .toString()
    .trim()
    .split(' ')
    .map((val) => parseInt(val));

const n = input[0];
const m = input[1];

const mySolution = (n, m) => {
    const getCount = (num, k) => {
        cnt = 0;

        while (num) {
            num = parseInt(num / k);
            cnt += num;
        }

        return cnt;
    };

    const twoCnt = getCount(n, 2) - getCount(m, 2) - getCount(n - m, 2);
    const fiveCnt = getCount(n, 5) - getCount(m, 5) - getCount(n - m, 5);

    return Math.min(twoCnt, fiveCnt);
};

console.log('mySolution', mySolution(n, m));

---

문제 풀이

 nCr = n!/(n-r)!r! 이라는 공식을 이용하면 되는 문제이다. 하지만 단순 팩토리얼을 구현하면 문제에서 주어진 n 혹은 m이 20억이 될 수 있으므로 시간초과가 뜬다. 따라서 팩토리얼 0의 개수를 구할 때의 요령으로 문제를 푼다. 이때 팩토리얼 0의 개수에서는 5의 배수 개수만 구했다면 이번 문제에서는 2의 배수 개수도 같이 구한다.

---

함께 보기

https://gdk01.tistory.com/230

[Baekjoon] 1676 팩토리얼 0의 개수(파이썬/자바스크립트/NodeJs)

https://webruden.tistory.com/1054

[백준, node.js] 2004번 "조합 0의 개수" 문제 해결방법

https://tmdrl5779.tistory.com/95

[백준] 2004번 (python 파이썬)