백준 1676 - 팩토리얼 0의 개수 [파이썬]

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

1676번: 팩토리얼 0의 개수

 

풀이 과정

최대 500!까지 들어올 수 있는데 500!을 실제로 구하고 10으로 나눠보면서 뒤에 0이 몇번 나오는지 세기에는 500!이 너무 크다. 다른 방법을 생각해보자

 

N!에서 처음 0이 아닌 숫자가 나올때 까지의 0의 개수

=> N!이 10으로 나누어 떨어지는 횟수

=> N!을 소인수분해하고 나온 2의 개수를 a, 5의 개수를 b라 하면 => min(a, b) = N!이 10으로 나누어 떨어지는 횟수이다

 

그런데 N! = N * (N-1) * (N-2) * ... * 1고 우변에서 5가 인수로 들어가는 횟수가 2가 인수로 들어가는 횟수보다 항상 적다.

따라서 우변에서 5가 인수로 몇번 들어가는지 세주면 된다.

 

소스 코드

def factorial_count(n):
    count5 = 0
    while n >= 1:
        if n % 125 == 0: count5 += 3
        elif n % 25 == 0: count5 += 2
        elif n % 5 == 0: count5 += 1
        n -= 1
    return count5


N = int(input())
print(factorial_count(N))