[백준 1676번] (factorial)팩토리얼 0의 개수 in python

문제

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

입력

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

출력

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

예제 입력 1

10

예제 출력 1

2

예제 입력 2

3

예제 출력 2

0

---

처음에 어떤 의미의 문제인가 이해를 하지 못했다.

그러다 계산기로 10!을 쳐보고 이해를 했다.

5!=120

10!=3,628,800

즉 뒤에 있는 0의 갯수를 말하는 것이였다.

10!은 5의 배수인 5와 10이 두개이므로 0이 2개가 나온다.

15!는 5,10,15 3개이므로 0이 3개가 나온다.

그렇기에 5만 나올때마다 cnt+=1해주면 될줄 알았다....

n=int(input())
cnt=0
for i in range(0,n+1,5):
  if i==0:
    continue
  cnt+=1
print(cnt)

하지만 문제가 있었다....

 

5,25,125가 5의 배수 카운트보다 더 0은 증가했다.

25!=15,511,210,043,330,985,984,000,000

 

이처럼 0이 6개가 왔다ㅜㅜㅜ

 

이 원리를 검색해 보면 이렇다..

25는 5x5로 5를 두개 가지고 있다. 그렇기에 25의 배수는 5를 한번더 카운트해줘야한다.

즉 25,50,75,100이 될때매다 5가 하나씩 더 늘어난다. == 0이 하나씩 더 늘어난다는 소리이다.

 

그런 100!은

5일 때, 0이 5,10,15,20~100 까지 총 20개

25일 때, 25,50,75,100 까지 4개 

합쳐서 총 24개의 0이 생긴다.

 

그럼 이와 같이 125는 5x5x5로 5가 3개이므로, 125, 250, 375, 500 일 때도 5를 하나씩 추가해줘야한다는 소리이다.

예를 들어 500!일 경우

5일 때, 5,10,15~~~500까지 100개

25일 때, 25,50,~~500까지 20개

125일 때, 125,250,375,500까지 4개

총 124개의 0이 있다.

 

n=int(input())

cnt=0
while n>0:
  cnt+=n//5
  n//=5

print(cnt)

코드를 짜면 이와 같다.

또한 다른 분의 코드를 보니 딱 2줄로 끝낸 것이 있었다.

https://hwiyong.tistory.com/360

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

 

 

답을 보면 이해를 하겠지만 막상 내가 풀자니 이런 조건들을 찾아낼 수 있을지 의문이다.

 

 

---

여담으로 n!을 구하는 라이브러리 또한 있다.

from math import factorial

n=5
result=factorial(n)

print(result)

# 결과 : 120