[백준] 1676번 팩토리얼 0의 개수 - Python / 알고리즘 기초 1/2 - 수학 1

---

---

---

💡 문제

N!에서 뒤에서부터 처음 0이 아닌 숫자가 나올 때까지 0의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다. (0 ≤ N ≤ 500)

출력

첫째 줄에 구한 0의 개수를 출력한다.

---

💭 접근

팩토리얼을 인수분해 했을 때, 0이 늘어나는 순간은 $10(2 \times 5)$이 곱해질 때이다. 따라서, 2와 5의 개수를 찾는 문제이다. 이때 5가 더 적게 곱해지므로 5의 개수만 찾으면 총 0의 개수를 찾을 수 있다.

ex)
$5! = 1 \times 2 \times 3 \times 4 \times 5$
-> 5 (1개)
$10! = 1 \times 2 \times 3 \times 4 \times 5 \times 6 \times 7 \times 8 \times 9 \times 10$
-> 5, 10(2개)

이때 주의해야 할 점으로 $25(5 \times 5)$는 5가 2개, $125(5 \times 5 \times 5)$ 이므로 3개를 더해주어야 한다. (입력의 최대가 500이므로 125 이상을 고려하지 않는다.)

---

📒 코드

n = int(input())
print(n//5 + n//25 + n//125)

---

💭 후기

소인수분해의 특성과 언제 10이 곱해지는지를 잘 생각하면 되는 문제.

---

🔗 문제 출처

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

---