[백준/Python] 3474번 교수가 된 현우

문제

 

https://www.acmicpc.net/problem/3474

3474번: 교수가 된 현우

---

Algorithm

 

당연히 팩토리얼을 구하고 끝의 0의 개수를 구하면 시간초과가 나온다! 1 <= N <= 1000000000이니깐..

오른쪽 끝에 있는 0의 개수는 n!안에 들어있는 10의 개수를 생각해보면 된다. 10 = 2*5이므로 n!안에 있는 2와 5의 개수를 구하고 그 둘중 작은게 될것이다. 

더 생각해보면 n!안에는 2의개수가 5의개수보다 많을 거라고 생각한다. 결국 우리는 n!안에 들어있는 5의개수를 구하면 된다.

예로 25!을 봐보자. 25!안에 있는 5의배수는 5,10,15,20,15 총 5개이고, 25는 5의 제곱이므로 총 6개이다.

그러면 n을 5**1로 나눈 개수 + n을 5**2로 나눈 개수 + n을 5**3으로 나눈 개수 + ... 를 하면 값이 나오게 된다.

코드를 보면 n안에 5가 몇개 있는지 찾는 함수를 만들어준다. 그 후에는 테스트케이스 t를 입력받고 정수n을 입력받고 함수에 넣은 값을 출력하면 된다!

---

 

 

Code

input = __import__('sys').stdin.readline
import math
def find_fives(n): #n!안에 들어있는 5의 개수를 구하는 함수 
    t=5
    cnt=0 #n!안에 들어있는 5의개수를 담을 변수
    while t <= n: #n을 5의거듭제곱으로 나누는데 5의거듭제곱이 n보다 커지면 반복문 종료
        cnt+= n//t
        t*=5
    return cnt #변수 리턴
n = int(input())

for i in range(n):
    t = int(input())
    print(find_fives(t))