알고리즘-문제풀이
[boj] 1676. 팩토리얼 0의 개수
hy1as
2023. 3. 15. 15:29
[boj] 1676. 팩토리얼 0의 개수
- 문제 링크 : https://www.acmicpc.net/problem/1676
- 사용 언어 : Node.js
1676번: 팩토리얼 0의 개수
N!에서 뒤에서부터 처음 0이 아닌 숫자가 나올 때까지 0의 개수를 구하는 프로그램을 작성하시오.
www.acmicpc.net
$ 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))
마치며
문제 풀이 시 주어진 데이터가 메모리나 프로그래밍 언어의 자료형을 초과하지 않는지 주의 깊게 살펴봅시다.