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

📩 출처

문제

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

입력

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

출력

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

👉 생각

• 직접 n!을 계산해주어서 문자열로 바꾼뒤 뒤에서 부터 0의 개수를 카운트 해주었다

n = int(input())

total = 1
for num in range(2, n+1):
    total *= num
number = str(total)[::-1]
cnt = 0
for i in number:
    if i != '0':
        break
    cnt += 1
print(cnt)

• 위 방법보다 더 효율적인 방법으로, n!을 인수 분해 했을 때 0이 생기는 순간은 (2x5)가 곱해지는 순간이다.
• 즉, n!에서 5의 배수들이 곱해지면 0이 1개 붙게 된다. 25(5x5)의 배수를 곱하면 0이 2개 붙고, 125(5x5x5)의 배수를 곱하면 0이 3개 붙게된다.
• 따라서 n!을 각각 5, 25, 125로 나누었을 때 몫을 더해주면 0의 개수를 찾을 수 있다

n=int(input());print(n//125+n//25+n//5)