[boj] 2004. 조합 0의 개수

[boj] 2004. 조합 0의 개수

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

2004번: 조합 0의 개수

$ n \choose m $에서 뒤에서부터 처음 0이 아닌 숫자가 나올 때까지 0의 개수를 구하는 프로그램을 작성하시오.

---

 

1. 문제 분석

주어진 조합의 값에 대한 뒤에서부터의 0의 개수를 구하는 문제입니다.
우선 조합의 값을 구하는 공식을 이해하고 있어야 합니다.
서로 다른 $ n $ 개에서 순서를 생각하지 않고 $ m $ 개를 선택하는 것을 개를 선택하는 것을 $ n $개에서 $ m $개를 택한 조합이라 하고 $ {}_n \mathrm{ C }_m $ 과 같이 나타냅니다.
$ {}_n \mathrm{ C }_m = \frac{n!}{m!(n-m)!} $ 과 같이 계산할 수 있습니다.
n, m 의 범위가 20억이기 때문에 $ factorial(N) $ 계산은 프로그래밍 언어 자료형의 크기를 초과하여 불가능합니다.
때문에 $ factorial $ 연산을 하지 않고 연산 과정에서 나오는 수들만으로 해결해야 합니다.
예를 들어 $ factorial(N) $ 값이 194000이라면 $ 194\times10^3 $과 같이 나타낼 수 있습니다.
즉, 뒤에 나오는 0 의 개수는  $ 10^x $ 로 나타낼 수 있다는 것을 알 수 있습니다.
그렇다면 연산 중에 나오는 10의 개수는 어떻게 구할 수 있을까요?
이는 연산 중에 나오는 수 들을 소인수분해 해서 2와 5의 묶음 개수를 세어주면 됩니다.
분자에 위치한 2와 5의 개수는 더해주고 분모에 위치한 2와 5의 개수는 빼주어 2와 5의 총개수를 세어줍니다.
2와 5의 쌍만큼 결과값에 '0'이 출현하게 됩니다.

 

---

 

2. 솔루션

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 $ 이 증가하면 수의 크기가 기하급수적으로 증가합니다.
팩토리얼 연산이 문제에서 보일 땐 계산해야 하는 값이 프로그래밍 언어의 자료형의 크기를 초과할 가능성이 농후하므로 소인수분해의 개념을 활용합시다.