백준 js 1676: 팩토리얼 0의 개수

개발👩‍💻/알고리즘

gigibean 2021. 5. 6. 15:29

728x90

문제

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

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

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

0이 올 수 있는 것은 10^n 인 수에서 가능하다.

예를 들어 100라는 수가 있다면, 100 = [10^2] = [[5*2]^2] = [5*2 * 5*2]로 표현이 가능하고,

이러한 수의 개수를 찾기위해서는 이렇게 5*2를 만들 수 있는 5가 몇개 있는지 찾아보면 된다. (x! 에서 2는 항상 5보다 많거나 같기 때문)

예를 들어 10!이라는 수가 있다고 해보자

10! = 1 * 2 * ... * 5 * ... *10 이렇게 표현할 수 있다.

여기서 5가 있는 수를 찾아보면 [5*1], [5*2] 가 있다.

그러므로 이 10!의 끝자리 0의 개수는 2개라고 추측할 수 있는데,

실제로 계산해보면 3628800로 0이 2개 인 것을 알 수 있다.

const n = 주어진 수
let result = 0
for (let i = 5; i <= n; i+=5) {
	result += 1;
}

더 큰 수인 100!을 예시로 들어보면

100!에서 5의 배수를 보면 5,10,..25,..100이렇게 있다.

여기서 중요한 것은 25, 50,75,100같은 수이다.

이 수들은 5*5, 5*5*2,.. 식으로 5가 두번 들어가게 된다.

이렇게 5가 다중으로 들어가는 수는 다시 0의 자리를 만들기 때문에 이를 모두 계산 해주어야 한다.

const n = 주어진 수
let result = 0;
for (let i = 1; i <= n; i++) {
	for (let j = Math.pow(5,i); j <= n; j+=Math.pow(5,i)) {
    	result +=1;
    }
}

위의 코드로 계산을 해보면,

i = 1일 때,

25를 만다 result +=1 이되고,

I = 2 일 때

Math.pow(5,2)로 25를 만나

다시 result += 1 이 되기 때문에

총 2번 result에 담기게 된다.

그래서 5^x (x>= 2) 인 모든 수를 소인수분해하여 계산하는 것처럼 표현할 수 있다.

그리고 이를 더 간단한 코드로 풀 수 있는데,

위 예시처럼 5의 배수 개수, 25의 배수 개수,.. 를 모두 구하기 전에 각 배수의 개수를 생각해보면

100에서 5의 배수의 개수는 총 20개 이다.

100/5 = 20

100에서 25의 배수의 개수는 총 4개이다.

100/25 = 4

그렇기 때문에 따로 2 deep 루프를 통해서 값을 증가시킬 필요 없이 n/i로 충분히 해당 배수의 개수를 구할 수 있다.

result += parseInt(input/5);
result += parseInt(input/25);

그리고 5의 배수를 증가시켜주는 루프만 추가해주면 된다.

for(let i = 5; i <= n; i*=5) { // 5, 25, ..
	result += parseInt(n / i)
}