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

문제

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

풀이 1 (내 풀이)

def fac(x):
    return 1 if x <= 1 else x * fac(x-1)

num = fac(int(input()))
cnt = 0
for i in str(num)[::-1]:
    if i == '0':
        cnt += 1
    else: 
        break
print(cnt)

1. 재귀 함수로 팩토리얼을 구하는 함수 fac 정의
2. N!을 구해 num에 저장
3. num을 str로 형변환하여 끝에서부터 한 문자씩 가져와, '0'일 경우 cnt += 1

풀이 2 (참고)

N = int(input())
print(N//5 + N//25 + N//125) 

# 0 ≤ N ≤ 500 이므로 5^3 = 125까지만 고려하면 된다. (5^4 = 625 > 500)
# 예시 1) 25! -> 5+1+0=6
# 예시 2) 30! -> 6+1+0=7

• 0이 늘어나는 순간 = 10(=2*5)이 곱해졌을 때
• 즉 N!에 포함된 5의 개수를 찾으면 된다. (2의 개수가 5의 개수보다 항상 많으므로)
  • 예시 1) 5! = 1*2*3*4*5 -> 5가 1개 -> 0이 1개
  • 예시 2) 10! = 1*2*3*4*5*6*7*8*9*10 -> 5가 2개(5, 10=5*2) -> 0이 2개

0! ~ 4! -> 0이 0개
5! = 120 -> 0이 1개; 5
...
10! = 3628800 -> 0이 2개; 5, 10
...
15! = 1307674367000 -> 0이 3개; 5, 10, 15
...
20! = 2432902...40000 -> 0이 4개; 5, 10, 15, 20
...
25! = 1551121...4000000 -> 0이 6개; 5, 10, 15, 20, 25(=5*5)
...
30! = 5, 10, 15, 20, 25, 30 -> 5가 7개 -> 0이 7개

---

교훈

• 항상 수학으로 접근하려고 시도해보자.