[BOJ] 1676번: 팩토리얼 0의 개수 (feat. python)

- 문제

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

- 입력

• 첫째 줄에 N이 주어진다. (0 <= N <= 500)

- 출력

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

- 예제 입력

	예제 입력	예제 출력
1	10	2
2	3	0

---

- 풀이

가장 먼저 떠올리기 쉬운 풀이 방법은 다음과 같다.
1. N! 계산
2. 계산된 값을 str으로 변환
3. 문자열의 뒤에서부터 0의 갯수를 카운팅
4. 카운팅 된 갯수를 출력

그러나, 위와 같은 방법으로 문제를 풀면 오답으로 처리된다.
즉, 다른 방식으로 문제를 풀어야 한다.
이 부분에서 수학적인 해석이 필요하다.

5!, 10!을 예시로 들어서 얘기해보면,

$5!=1 \times 2 \times 3 \times 4 \times 5 = 120$
5!을 계산하는 과정에서 곱해지는 5의 갯수는 1개이고, 계산된 5! 값에서 0의 갯수는 1개이다.

$10! = 1 \times 2 \times 3 \times 4 \times 5 \times 6 \times 7 \times 8 \times 9 \times 10 = 3628800$
10!을 계산하는 과정에서 곱해지는 5의 갯수는 2개이고, 계산된 10! 값에서 0의 갯수는 2개이다.
(위 예시에서 5의 갯수가 2개인 이유는, $10 = 2 \times 5$로 분해할 수 있기 때문)

위 두 예시를 살펴보면, 다음과 같은 규칙을 확인할 수 있다.
N!을 계산할 때 사용된 5의 갯수는 계산된 숫자 뒷 부분에 나오는 0의 갯수와 동일하다

따라서, N!을 계산할 때 곱해지는 5의 갯수를 확인하면 0의 갯수를 계산할 수 있다.

추가적으로, N의 값을 입력 받을 때, input() 함수를 사용하면 시간 초과가 발생한다.
따라서, sys 모듈을 사용해야 한다.

- 소스코드

import sys
input = sys.stdin.readline

n = int(input())

count = 0
while n > 0:
    count += n // 5
    n //= 5

print(count)