백준 1676 : 팩토리얼 0의 개수 (파이썬)

팩토리얼 0의 개수

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
2 초	128 MB	36812	17491	14523	47.923%

문제

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

입력

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

출력

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

예제 입력 1

10

예제 출력 1

2

예제 입력 2

3

예제 출력 2

0

---

코드

#https://teching.tistory.com/

n = int(input())
fac = 1
for i in range(1,n+1):
    fac *= i
fac = str(fac)
answer = 0
for i in range(len(fac)-1,-1,-1):
    if fac[i] != '0': break
    answer += 1
print(answer)

해설

처음에는 단순하게 팩토리얼을 구한 뒤 뒤에서부터 0의 개수를 세어주었다.

가볍게 풀리긴 했지만 정수론에 위치하는 이유가 있을 것 같아 고민을 해보았다.

고민을 해보았더니 수를 분해했을때 10의 개수가 0의 개수였다, 즉 소인수 분해했을 때 2와 5가 동시에 오는 개수가 뒤에서부터 0개 개수가 된다.

예를 들어 320를 소인수 분해하면 2^6 * 5이다.

여기에 팩토리얼은 결국 N! 은 1부터 N까지 모두 곱한 것이다. 그러므로 각 숫자들에 포함되어있는 2, 5의 개수를 찾으면 된다.

예를 들어 10! = 10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1인데 5의 배수는 5, 10이므로 10은 총 2개가 온다.

확인하기 위해 각 숫자를 소인수분해해주면

(2*5) * (3*3) * (2*2*2) * 7 * (2*3) * 5 * (2*2) * 3 * 2 * 1이다. 2의 개수는 총 8개, 5의 개수는 2개 이므로 10은 2개가 온다. 또한 팩토리얼 안에서는 2의 배수가 5의 배수보다 항상 많기 때문에 5의 배수의 개수만 세주면 10이 몇 번 곱해지는지 알아낼 수 있다.

이러한 원리를 이용해 코드를 다시 작성해 보았다.

코드 2

#https://teching.tistory.com/

n = int(input())
cnt = 0
f = 5
while f <= n:
    cnt += n//f
    f *= 5

print(cnt)

주의할점은 25, 125... 는 5의 개수가 2개, 3개... 있는 숫자이므로 추가적으로 25의 배수개수를 더해주고 125의 배수를 더해주고 해야한다. 이렇게 해주면 125는 25와 5의 배수이기도 하므로 최종적으로 3번을 더해준 것이 된다.

이렇게 n!를 소인수 분해 했을때 5의 개수를 찾아주면 된다.