핵심

• 결과값에서 0의 개수는 2 x 5 한쌍이 만들어질때마다 생김
• 주어진 수를 소인수분해 했을때 5의 지수를 찾는것
  • 2의 지수는 항상 높을 수 밖에 없음

첫번째 풀이

• 시간 초과
• 하나씩 5의 배수인지 확인하고 값을 저장
• 주어진 수를 n 이라고 할 떄, 1..n 까지 순회하면서
  • 5로 나눠진다면
  • dict[n/5] 가 존재하는지 확인
    • 존재한다면
      • dict[n] = dict[n/5] + 1
    • 존재하지 않는다면
      • dict[n] = 1
• dict 를 사용해서 이전 연산을 줄였다고 생각했는데 오래걸림
  • 1억까지 순회해서 그런가?

두번째 풀이

• 강의 해설
• N! 의 결과값이 있을 때 소인수분해 했을때 어떤 소인수 z 의 지수값은
  • N을 z 으로 나눈 값
  • N을 z^2 으로 나눈 값
  • N을 z^3 으로 나눈 값
  • …
  • 을 모두 더한 값임
• 즉, 30! 에서 5의 지수값을 구하려면
  • 30을 5로 나눈 값 = 6
  • 30을 25로 나눈 값 = 1
  • 30을 125로 나눈 값 (30이 넘어갈때부터는 0이므로 의미 없음)
  • 모두 더한 값 7이 된다는 말씀

<aside> 📌 이런 특징이 있구나~~ 걍 외워

</aside>