[Python] 1676 - 팩토리얼 0의 갯수

풀이

기존의 정석 풀이대로라면 N!을 구해서 10을 나눠 0을 구하는 방식을 사용했을 것이다.

하지만 문제에서 입력에 제한을 두었기 때문에 위와 같은 방식으로는 접근이 불가능하다. (500!을 계산하기 위한 메모리 부족)

그렇기에 다른 방식으로 접근을 해야 하는데, 그 방법은 다음과 같다.

1. 팩토리얼로 얻을 수 있는 수가 0이 증가할 때는 5의 배수가 곱해질 때 이다.
    1-1. 4! = 4 * 3 * 2 * 1 = 24, 0 / 5! = 5 * 4 * 3 * 2 * 1 = 720, 1
2. 따라서 우리는 입력받은 수에 대해 5의 갯수를 찾는 문제가 된다.
3. // 연산자를 이용해 몫만을 구하고, 나머지는 버린다.

# 1676 팩토리얼 0의 갯수

n = int(input())
count = 0

while(n>1):
    count = count + n // 5
    n = n // 5

print(count)