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

[백준] 1676번

팩토리얼 0의 개수

PYTHON

백준 1676번

어떤 팩토리얼 값에서 뒤에 이어지는 0의 개수를 구하는 것은

다시 말하면 10이 몇 번 곱해졌는지 묻는 문제와 동일하다.

또한 10이 몇 번 곱해졌는지 묻는 문제는 결국 소인수 분해를 한 경우
5가 몇 번 나타는 지 구하는 것과 동일하다.

2가 5보다 무조건 많이 등장할 것이기 때문이다.

팩토리얼이 아닌 일반적인 값이었다면 2와 5의 개수 중 더 적은 것을 택해야 한다.

---

Factorial 함수를 이용하는 방법

실제로 팩토리얼 값을 구해서 이 값을 10으로 나누는 것을 반복하는 것으로 0의 개수를 구할 수 있다.

팩토리얼은 math 라이브러리의 factorial 함수를 이용해서 구할 수 있다.

이 방법이 가능한 이유는 입력 값 n의 범위가 0~500으로 비교적 작은 값이라 시간 초과가 발생하지 않기 때문이다.

소스 코드를 살펴보자.

---

5의 개수를 구하는 방법

소인수의 개수를 구하는 방법의 예시는 다음과 같다.

N!의 소인수 분해시 5의 개수를 구하려면

1. 5의 배수의 개수를 구하기
2. 5^2의 배수의 개수를 구하기
3. ...
4. 5^i의 배수의 개수를 구하기

예를 들어 25!의 5의 개수는
1. 25/5 = 5 => 5,10,15,20,25
2. 25/25 = 1 => 25 로
소인수 분해 했을 때, 5가 총 6개 존재한다.

이 과정을 소스 코드로 나타내면 아래와 같다.

5의 제곱수의 배수를 구할 것이기 때문에 N 값을 계속 5로 나누어주면 된다.