1676: 팩토리얼 0의 개수 - Python

문제

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

풀이 1 (오답, recursionError 발생)

def Factorial(n): # 팩토리얼 구하기(재귀함수)
    if n == 1:
        return 1
    else:
        return n * Factorial(n-1)
    
num = Factorial(int(input())) # ex) 10 입력 시, num = 3628800
cnt = 0
for i in str(num)[::-1]: # ex) '0088263'에서 하나씩 꺼내어
    if i == '0': # '0'이면 cnt 증가
        cnt += 1
    else: # '0'이 아니면 for문 탈출
        break
print(cnt) # '0' 개수 출력

# 풀이 과정
1. 재귀함수로 Factorial을 구현한다.
2. 입력한 수(num)의 Factorial을 구한다.
3. 구한 Factorial을 뒤집힌 문자열로 만들고, '0'의 개수를 구한다.

RecursionError가 발생하였다.
따라서 Factorial 함수를 for문으로 수정해주었다.

풀이 2 (정답)

def Factorial(n):
    result = 1
    for i in range(1, n+1):
        result *= i
    return result
    
num = Factorial(int(input()))
cnt = 0
for i in str(num)[::-1]:
    if i == '0':
        cnt += 1
    else:
        break
print(cnt)

Factorial 계산 시 math.factorial() > for문 > 재귀함수 순으로 빠르다고 하다.

풀이 3 (참고)

n = int(input())
cnt = 0

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

print(cnt)

감탄스럽다..

• 5!, 10!, 15!, ... 등 5가 곱해질 때마다 0이 증가한다.
• 이때 제곱수(25, 125 등)를 고려한다.

---

오늘의 교훈

• 무작정 풀기보다는 수학적 규칙을 발견해보자.
• 예를 들어, 이 문제의 경우에서는 수열로 나열한 뒤 규칙을 찾아보자.

참고 자료

Python Factorial 속도 비교