[🥈4 / 백준 1676 / 파이썬] 팩토리얼 0의 개수

 

1676번: 팩토리얼 0의 개수

 

문제

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

입력

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

출력

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

 

예제 입력 1  10	예제 출력 1  2
예제 입력 2  3	예제 출력 2  0

 

풀이

 

팩토리얼을 계산했을 때, 맨 뒷자리에 연속된 0이 몇 번 나오는지 세는 문제이다.

문제 설명에 소인수분해의 성질을 이용하라는 데에서 힌트를 얻었다.

 

보통 수의 끝자리에 0의 개수를 늘리기 위해서는 곱하기 10을 해주면 된다.

여기서 10은 2 * 5 꼴로 나타낼 수 있다.

 

이미 수를 소인수분해 했을 때 2의 개수가 5의 개수보다 많다면?

그냥 5만 곱해주면 된다.

 

여기서, 팩토리얼의 특성 상 소인수분해했을 때, 2의 개수가 5의 개수보다 항상 많으므로

해를 구하기 위해서는 그냥 소인수분해했을 때 5의 개수가 몇인지만 세면 된다.

 

단, 팩토리얼을 계산한 뒤 소인수분해하고 이를 세는건 성능상 매우 비효율적이므로

계산은 그냥 생략해버리고 곱할 때 5로 나누어 떨어지는 횟수만 세자 ㅎㅎ

 

count = 0

for i in range(int(input()) + 1):
    while(i % 5 == 0 and i > 0):
        count += 1
        i //= 5
print(count)