(boj) 2004. 조합 수 0

(boj) 2004. 조합 수 0

• 문제 링크: https://www.acmicpc.net/problem/2004
• 사용 언어: Node.js

$ n \choose m $에서 끝에서부터 0이 아닌 첫 번째 숫자까지 0의 개수를 세는 프로그램을 작성하세요.

1. 문제 분석

문제는 주어진 값 조합 뒤에 있는 0의 개수를 찾는 것입니다.
먼저 조합 값을 계산하는 공식을 이해해야 합니다.
순서를 고려하지 않고 다른 $n$ 조각에서 $m$ 조각을 선택하는 것을 $n$ 조각에서 $m$ 조각을 결합하는 것으로 ${}_n \mathrm{ C }_m$는 방법을 나타냅니다.
$ {}_n \mathrm{ C }_m = \frac{n!}{m!(nm)!} $
n과 m의 범위가 20억이므로 $factorial(N)$을 계산하는 것은 프로그래밍 언어 데이터 타입의 크기를 초과하기 때문에 불가능하다.
따라서 계승 연산을 수행하지 않고 계산 과정에서 나온 숫자만 풀면 된다.
예를 들어 $factorial(N)의 값이 $194000이면 $194\times10^3$로 표현할 수 있습니다.
즉, 뒤에 오는 0의 개수는 $10^x$로 표현할 수 있음을 알 수 있습니다.
그렇다면 연산 중에 나타나는 10의 갯수는 어떻게 알 수 있을까요?
이는 작업 중에 나타나는 숫자를 인수분해하고 2와 5의 그룹 수를 세어 수행할 수 있습니다.
분자에 있는 2와 5의 수를 더하고 분모에 있는 2와 5의 수를 빼서 2와 5의 총 수를 구합니다.
2와 5의 쌍은 ‘0’을 제공합니다.

두 번째 솔루션

const fs = require('fs');
const (n, m) = fs.readFileSync(process.platform === 'linux' ? '/dev/stdin' : 'input.txt').toString().trim().split(' ');

function getCountOfDivider(target, divider) {
    let countOfDivider = 0;
    let currentDividerValue = divider;
    while(currentDividerValue <= target) {
        countOfDivider += Math.floor(target / currentDividerValue)
        currentDividerValue *= divider
    }
    return countOfDivider
}

// 분자의 n!
const countOfTwoInNumerator = getCountOfDivider(n, 2)
const countOfFiveInNumerator = getCountOfDivider(n, 5)

// 분모의  m! + (n-m)!
const countOfTwoInDominator = getCountOfDivider(m, 2) + getCountOfDivider(n-m, 2)
const countOfFiveInDominator = getCountOfDivider(m, 5) + getCountOfDivider(n -m, 5)

// 분자의 n!의 2의 개수 - 분모의 m!과 (n-m)! 의 2의 개수
const countOfTwo = countOfTwoInNumerator - countOfTwoInDominator;

// 분자의 n!의 5의 개수 - 분모의 m!과 (n-m)! 의 5의 개수
const countOfFive = countOfFiveInNumerator - countOfFiveInDominator;

// 2와 5의 쌍의 개수
console.log(Math.min(countOfTwo, countOfFive));

마지막으로

계승 연산은 $N$이 증가함에 따라 숫자의 크기를 기하급수적으로 증가시킵니다.
문제에 계승 연산이 표시되면 계산할 값이 프로그래밍 언어 데이터 유형의 크기를 초과할 확률이 높으므로 소인수 분해 개념을 사용합니다.