[백준] 1676번 팩토리얼 0의 개수 해설 및 풀이 (Python)

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

https://www.acmicpc.net/problem/1676

 

---

문제

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

입력

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

출력

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

 

문제 유형

수학

---

풀이 방법 도출

 

팩토리얼(N!)을 계산한 뒤, 뒤에서부터 몇 개의 0이 연속적으로 있는지를 확인하는 문제입니다.

예를 들자면 10!은 3628800입니다. 뒤에서부터 2개의 0이 있기 때문에 결과값이 2를 가집니다.

 

팩토리얼 수에서 0이 나오는 이유는 10이 곱해졌기 때문입니다. 따라서 2와 5가 곱해질 때마다 10이 생깁니다.

하지만 팩토리얼을 직접 계산하고 0을 세는 방법은 숫자가 커질수록 비효율적입니다.

더 좋은 방법은 5의 배수의 개수만 세는 것입니다.

 

즉, N을 5로 나눈 몫 + N을 25로 나눈 몫 + N을 125로 나눈 몫 + ...을 더하면 0의 개수를 구할 수 있습니다.

 

시간 복잡도

• 팩토리얼 : O(N)
• count_zero : O(log N)

---

핵심 코드 삽입 및 설명

import sys


input = sys.stdin.readline


# N 입력 받기
N = int(input())


# 팩토리얼(N!) 계산 함수
def factorial(n):
    result = 1
    for i in range(1, n + 1):
        result *= i
    return result


# 끝자리 0의 개수를 세는 함수
def count_zero(n):
    result = 0
    # 끝자리가 0일 때마다 10으로 나누어 0의 개수 카운트
    while n % 10 == 0:
        result += 1
        n //= 10
    return result


# 결과 출력
print(count_zero(factorial(N)))