[실버] 팩토리얼 0의 개수 성공 (1676번)_JS

문제

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

 

입력

첫째 줄에 N이 주어진다. (0 ≤ N ≤ 500)

 

출력

첫째 줄에 구한 0의 개수를 출력한다.

 

 

---

 

오랜만에 백준 문제를 풀며 난이도를 낮추어 한번 풀어보자 하고 도전한 문제..

만만하게 그냥 팩토리얼 돌렸다가 역시나 수가 너무 커서 답이 나오지 않았다.

그럼 어떻게 해야하나 고민하던 차 검색을 해 해답을 얻었다.

 

[C] 백준 1676번 팩토리얼 0의 개수

 

여기에서 굉장히 잘 설명해준다.

 

간단하게 내가 이해한 바로는

만약 팩토리얼의 결과가 N 일 때 이걸 모두 소인수분해하면,

N(30) = 2 x 3 x 5,

N(1,200) = 2^4 x 3 x 5^2,

N(7,560,000) = 2^6 x 3^3 x 5^4 x 7,

이런식이다.

 

여기에서 중요한 것은 (2 x 5)의 갯수인데,

끝 0의 갯수는 10으로 나머지 없이 몇번 나누어지냐는 것(= Math.min(2 소인수갯수, 5 소인수갯수))과 같다.

 

근데 소인수 2의 배수는 2, 4, 6, 8, 10,,,, 끝도 없이 많으니

상대적으로 적은 소인수 5의 갯수를 구하면 답이 나온다.

 

//

 

그럼 5의 갯수를 어떻게 구하느냐? input = 11 일 때,

숫자	11	10	9	8	7	6	5	4	3	2	1
소인수	11	2, 5	3^2	2^3	7	2, 3	5	2^2	3	2	-
소인수 5의 갯수	0	1	0	0	0	0	1	0	0	0	0
누적 소인수 5의 갯수	2개

이처럼 제시된 숫자 안에 5가 몇 개 들어가 있는 지를 세면 된다.

 

그런데 조심해야할 부분이 있다.

바로, 5의 제곱수들이다.

숫자	26	25	24	23	...	6	5	4	3	2	1
소인수	2, 13	5^2	2^3, 3	23	...	2, 3	5	2^2	3	2	-
소인수 5의 갯수	0	2	0	0	...	0	1	0	0	0	0
5가 몇개	Math.floor( 26 / 5 ) = 5 개
25가 몇개	Math.floor( 26 / 25 ) = 1 개
누적 소인수 5의 갯수	6개

이처럼 25같은 5의 제곱수는 소인수 5가 2개가 들어가있다.

 

때문에, 결과적으로는 

input 안에

5가 몇 개 들어가는지, (여기서 25의 소인수 5 중 하나 세고)

25가 몇 개 들어가는지, (여기서 25의 소인수 5 중 남은 하나 세는것)

125가 몇 개 들어가는지를 (125는 5^3이니까 이렇게 3번 세는 것)

계산하면 끝이 난다.

 

//

 

설명이 참 개똥같다.

하하

마지막으로 코드 올리고 마무리 한다.

둘 다 성공인데 아래가 조금 더 오래걸린다.. 왜일까..

const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "input.txt";
let input = fs.readFileSync(filePath).toString().trim();

function fiveCount(N) {
    let count = 0;

    let valOne = N % 5;
    count += (N - valOne) / 5;

    let valTwo = N % 25;
    count += (N - valTwo) / 25;

    let valThree = N % 125;
    count += (N - valThree) / 125;

    return count;
}

console.log(fiveCount(+input));

const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "input.txt";
let input = fs.readFileSync(filePath).toString().trim();

function fiveCount(N) {
    let count = 0;

    count += Math.floor(N / 5);
    count += Math.floor(N / 25);
    count += Math.floor(N / 125);

    return count;
}

console.log(fiveCount(+input));