알고리즘 기초 1/2. 300 - 수학1
2004번. 조합 0의 개수

문제

2004번 문제 링크

solution

const fs = require("fs");
let [n, m] = fs.readFileSync("/dev/stdin").toString().trim().split(" ").map((item) => Number(item));

function getTwoFive(num){
    let two = 0;
    let five = 0;

    for(let i = 2; i <= num; i *= 2){
        two += parseInt(num / i);
    }
    
    for(let i = 5; i <= num; i *= 5){
        five += parseInt(num / i);
    }
    
    return [two, five];
}

const [nTwo, nFive] = getTwoFive(n);
const [mTwo, mFive] = getTwoFive(m);
const [nmTwo, nmFive] = getTwoFive(n - m);

const two = nTwo - mTwo - nmTwo;
const five = nFive - mFive - nmFive;

console.log(Math.min(two, five));

이번 문제는 수학적 지식이 없다면 풀기 힘들 것 같다.
우선 조합(Combination)에 대해서 알아보자.

nCm = n! / ((n - m)! * m!)

위와 같은 공식으로 풀어내는 것이다.
하지만 저 식 그대로 코드로 풀어내면 메모리 초과가 발생할 것이다.
그래서 0의 개수만 알아내기 위한 방법을 알아야한다.

팩토리얼에서 뒤 부분에 0이 나오려면, 10이 곱해져야한다.
10은 2와 5의 곱으로 나타날 것이다.
예를들어, 2가 3개, 5가 2개 나온 상황이라면
10은 2개가 나오게 된다. 즉, 2와 5 중 더 적게 나온 것의 개수를 따라간다.
10이 2개 나왔으므로 100이 되고, 0의 개수는 2가 된다.

즉, 2와 5 중 작은 것의 개수만큼 10이 생성되고, 생성된 개수만큼 0이 나온다는 것이다.

이를 활용하여 팩토리얼 연산을 하는 각 숫자에 대하여 소인수분해를 해서 2와 5를 구한다.

조합 식에서 나누기 연산은 뺄셈으로 표현할 수 있다.
n에서의 개수에서 m과 n - m에서의 개수를 빼주면 된다.

그렇게 구한 2와 5 중 더 작은 개수가 0의 개수가 된다.

이러면 안된다

const fs = require("fs");
let input = fs.readFileSync("/dev/stdin").toString().trim().split(" ").map((item) => Number(item));

let n = input[0];
let r = input[1];

function factorial(num){
    if(num === 0 || num === 1){
        return 1;
    }
    
    return num * factorial(num - 1);
}

function newfactorial(num){
    if(num === 0 || num === 1 || num === r){
        return 1;
    }
    
    return num * factorial(num - 1);
}

// 조합(Combination, nCr)은 n! / ((n - r)! * r!)
// n은 r보다 크기 때문에 n!/r!은 n * (n-1) * ... * (r + 1) 이라고 할 수 있다.
let nFac = newfactorial(n);
let nMrFac = factorial(n - r);

let combination = nFac / nMrFac;

let combiArr = String(combination).split("");

let count = 0;

while(true){
    let popedNum = combiArr.pop();
    
    if(popedNum === "0"){
        count++;
        
        continue;
    }
    
    break;
}

console.log(count);

단순하게 조합 식에서의 각 팩토리얼을 구해서 연산하는 것으로는 정답을 맞출 수 없다.
필자는 스택 사이즈 초과 오류가 발생했다.
즉, 무지성으로 식만 따라 쓰면 안된다는 것이다.

참고 자료

참고 자료 1
참고 자료 2
참고 자료 3