[boj] 1676. 팩토리얼 0의 개수

[boj] 1676. 팩토리얼 0의 개수

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

1676번: 팩토리얼 0의 개수

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

---

1. 문제 분석

 $ factorial(N) $ 의 뒷 자릿수에 0이 몇 개 나오는지 세어보는 문제입니다.
주어진 문제의 N 최대값인 500을 factorial 연산을 하게 되면 프로그래밍 언어의 자료형을 초과하는 값이 나오게 되므로 factorial 연산을 하지 않고 연산 과정에서 나오는 수들만으로 해결해야 합니다.
예를 들어 팩토리얼 N 값이 194000 이라면 $ 194 \times 10^3 $ 과 같이 나타낼 수 있습니다.
즉, 뒤에 나오는 0 의 개수는 $ 10^x $로 나타낼 수 있다는 것을 알 수 있습니다.
그렇다면 연산 중에 나오는 10의 개수는 어떻게 구할 수 있을까요?
이는 연산 중에 나오는 수 들을 소인수분해 해서 2와 5의 묶음 개수를 세어주면 됩니다.
이때 2의 개수는 보다 5의 개수보다 항상 적게 나오기 때문에 5의 개수만 세어주면 되겠습니다.

 

---

 

2. 솔루션

const fs = require('fs')
const N = +fs.readFileSync(process.platform ===
                           'linux' ? '/dev/stdin' : 'input.txt').toString()

// Target : Factorial 의 N
// Divider : 소인수 분해 시 출현 하는 횟수 세고자 하는 수 => 이 문제에서는 '5'
function getCountOfDivider(target, divider) {
    //  '5'의 출현 횟수
    let countOfDivider = 0;
    // '5'의 제곱의 상황을 고려한 변수
    let currentDivider = divider
    // '5'의 x제곱이 N 보다 커지는 경우 중단
    while(currentDivider <= target) {
        // N에서 '5'의 x 제곱이 출현하는 횟수
        countOfDivider += Math.floor(target / currentDivider)
        // x + 1
        currentDivider *= divider;
    }
    return countOfDivider
}

console.log(getCountOfDivider(N, 5))

 

---

마치며

문제 풀이 시 주어진 데이터가 메모리나 프로그래밍 언어의 자료형을 초과하지 않는지 주의 깊게 살펴봅시다.