[백준] 1676번 - 팩토리얼 0의 개수

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

 

✔️ 문제

 

 

문제는 다음과 같다.

 

 

✔️ 풀이

 

 

팩토리얼을 math 라이브러리를 활용하여 구한 다음

문자열에 0이 나오면 break하고 개수를 반환할 수 있지만,

 

from math import factorial as f

n = int(input())
cnt = 0

for i in str(f(n))[::-1]:
  if i != '0': break
  cnt += 1

print(cnt)

 

수학적으로 계산하게 되면 n을 5로 나눴을 때 떨어지는

몫의 개수를 더한 값이 0의 개수가 될 수 있다.

 

예를 들면 10!은 3,628,800 수를 가지고 있고,

0이 아닌 수 8이 나오기까지 0의 개수 2개를 가지고 있는 것을

10을 5로 나눈 몫 2개와 같다고 볼 수 있다.

 

n, cnt = int(input()), 0

while n != 0:
  n //= 5
  cnt += n
  
print(cnt)

 

시간적으로는 아무래도 여러 방식이 아닌

수학적 방식의 접근이 4ms 더 빨랐다.

 

화이팅 💪