[백준 python 1676] 팩토리얼 0의 개수

[Silver V] 팩토리얼 0의 개수 - 1676

문제 링크

성능 요약

메모리: 33240 KB, 시간: 36 ms

분류

수학

제출 일자

2024년 10월 9일 18:08:24

문제 설명

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

입력

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

출력

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

풀이

import math

n = int(input())
f = str(math.factorial(n))
rev_f = str(int(f[::-1]))
print(len(f) - len(rev_f))

나의 풀이는 int형으로 변환하는 과정에서 앞에 `0`이 존재하면 지워지는 것을 활용하여 문제를 해결하였다.

먼저 입력받은 n의 팩토리얼을 구하여 문자열로 변환해준다. 그리고 숫자를 뒤집어진 것을 int로 변환한다.

예를 들어 10!이면 3,628,800이 나온다. 이를 역순으로 뒤집으면 0088263이 된다. 이를 int로 변환하게 되면 숫자로 되기 때문에 앞의 00이 없어지게 된다. 이 둘의 글자 수를 빼주게 되면 0의 개수를 알 수 있게 된다.

 

내가 푼 풀이는 뭔가 편법? 같다. 다른 사람들의 풀이를 확인해보니 5의 개수를 찾아서 0의 개수를 찾을 수 있는 것 같다.

해당 블로그를 확인했을 때, 0이 늘어나는 순간은 10을 곱할 때이다. 2보다 5가 더 적게 나오므로 5의 개수를 찾으면 된다고 한다.

그래서 다른 사람의 풀이를 확인해보면 이러하다.

n = int(input())
cnt = 0

while(n>1):
    cnt += n // 5
    n = n // 5

print(cnt)