[백준 1676] 팩토리얼 0의 개수 (Python) 풀이

https://www.acmicpc.net/ [출처]

---

1. 문제

 

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

 

 

2. 입력

 

N이 주어진다. (0 ≤ N ≤ 500)

 

 

3. 출력

 

0의 개수를 출력한다.

 

 

 

---

4. 풀이

 

N이 최대 500까지 존재하므로, 너무 큰 수인 500! 자체를 가지고 풀 수는 없다.

 

뒷자리 수에 0이 존재하려면, 약수에 10이 존재해야 한다.

 

0의 개수를 세자면 10^1 -> 1개, 10^2 -> 2개, ... 10^10 -> 10개라는 규칙이 있다.

 

N에 10이 몇 번 곱해졌는지 알기 위해서 소인수 분해를 생각했다.

 

10 = 2 * 5이므로 N을 소인수 분해 했을 때, 2와 5의 개수를 세면 되었다.

 

통상적으로 1 ~ N까지 곱한다고 했을 때, 소인수에 2가 5보다 많거나 같기 때문에 5의 개수만 세기로 했다.

 

(25 같은 경우는 5가 2번 곱해졌으므로, 5로 나누는 작업을 여러 번 해 줄 필요가 있다.)

 

 

5. 소스 코드

 

n = int(input())

fives = 0

for i in range(1,n+1):
    if i%5==0:
        k = i
        while k%5==0:
            fives +=1
            k/=5

print(fives)