[수학] 백준 2004 파이썬 (조합 0의 개수) 실버2

-풀이(시간 초과)

from math import factorial
count = 0
n, r = map(int, input().split())
bi = factorial(n) // factorial(r) // factorial(n-r)
bi = str(bi)
for i in bi[::-1]:
  if i != '0':
    break
  count += 1
print(count)

n, m이 20억이 될 수 있으므로 시간초과

-풀이

n, m = map(int, input().split())

def two_count(n):
    two = 0
    while n != 0:
        n = n // 2
        two += n
    return two

def five_count(n):
    five = 0
    while n != 0:
        n = n // 5
        five += n
    return five

print(min(two_count(n) - two_count(n - m) - two_count(m), five_count(n) - five_count(n - m) - five_count(m)))

 

-풀이 설명(느낀점)

[20분 no sol] 그냥 팩토리얼 구하는식으로 풀면 시간초과가 떴다. 다른 방법이 도저히 생각이 안나 구글링을 해보았다.

구글링 결과 문제해결 방법은 n!의 2와 5의 개수를 세주고 여기에 (n-r)!와 r!의 2와 5의 지수의 총합을 빼서 둘중에 더 작은 것을 고르면 답을 구할 수 있다.