0 이상 500 이하의 정수 n이 주어질 때,
n!의 일의 자리부터 연속되는 0의 개수를 구하는 문제이다.
n!을 문자열로 변환한 뒤,
조건문을 통해 0의 개수를 세는 방법을 떠올렸다.
파이썬에서 팩토리얼을 계산할 수 있는 방법은..
반복문, 재귀 함수, 내장 함수가 있다.
(https://velog.io/@jeonghens/%ED%8C%A9%ED%86%A0%EB%A6%AC%EC%96%BC-%EA%B3%84%EC%82%B0%ED%95%98%EA%B8%B0)
여기에선 내장 함수로 풀었다.
코드(정답)는 다음과 같다.
# 1676
import sys
import math
n = int(sys.stdin.readline())
facto_n = str(math.factorial(n))
cnt = 0
for num in facto_n[::-1]:
if num == '0':
cnt += 1
else:
break
print(cnt)위와 같은 단순한 흐름도 좋지만,
소인수분해를 이용한 풀이도 생각해 볼 수 있다.
(시간, 공간 복잡도 조건이 까다로워지면, 위의 풀이는 통과되지 못할 가능성이 있다.)
팩토리얼의 정의가 1부터 n까지 모든 수를 곱하는 것이다.
따라서 n을 소인수분해 했을 때,
'2와 5의 지수 최솟값'이 '구하고자 하는 0의 개수'이다.
근데 n!은 어떤 경우라도 5의 지수 값이 2의 지수 값보다 크거나 같다.
따라서 n을 소인수분해 했을 때 5의 지수 값이 정답이다.
n // 5: n 이하의 자연수 중 5의 배수의 개수
n // 25(5^2): n 이하의 자연수 중 25(5^2)의 배수의 개수
문제에서 n의 범위가 0 이상 500 이하이므로,
아래의 3가지 경우만 고려해 주면 된다.
(즉, n이 625 이상인 경우는 범위를 벗어나므로 고려할 필요가 없다.)
1) n을 5로 나눴을 때의 몫이.. 0의 개수
2) n을 25로 나눴을 때의 몫이.. 1)에서 포함되지 못한 지수 값이 2인 경우의 0의 개수
3) n을 125로 나눴을 때의 몫이.. 1), 2)에서 포함되지 못한 지수 값이 3인 경우의 0의 개수
간결해진 코드(정답)는 다음과 같다.
import sys
n = int(sys.stdin.readline())
print((n // 5) + (n // 25) + (n // 125))