백준 #3474 교수가 된 현우(Python)

백준 알고리즘 문제 3474번 교수가 된 현우 문제이다.

실버 4의 문제로 머리만 잘 굴리면 풀 수 있는 문제이다.(사실 모든 문제가 그렇긴 한데, 머릿속으로는 돼도, 구현이 쉽지 않지)

 

 

이 문제에서는 팩토리얼을 했을 때 나오는 0의 갯수를 구하라고 나와있다.

 

그러니까 5!을 하면 120이 나오니까 0이 한 개 인 것이다.

 

당연히 처음에는 모르니까 하나씩 적어보는게 편하다.

6! 은 720, 7! 은 5040(오른쪽 0갯수만 셈) 8!은 40320....

 

자세히 살펴보면 2와 5의 제곱의 짝의 갯수에 의해서 0의 갯수가 정해지는 것을 알 수 있다.

 

그럼 당연히 소인수 분해를 하면 2의 갯수는 5의 갯수보다 많기 때문에, 

 

결국 5의 제곱의 갯수만 구하면 되는 쉬운 형태로 결론이 난다.

 

그렇기 때문에 이를 다음과 같이 구현할 수 있다.

 

import sys

t = int(sys.stdin.readline())
for i in range(t):
    total = 0
    n = int(sys.stdin.readline())
    a = 5
    while a <= n:
        total += n // a
        a *= 5
    print(total)

 

참고로 파이썬 input()으로 받으면 시간초과가 발생한다.