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

문제

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

문자열을 이용한 풀이

입력받은 N을 팩토리얼 함수로 연산한 후, 그것을 문자열로 바꿔 끝에서 부터 0의 개수를 카운트 해준다.

Python 코드

import sys
from math import factorial
input = sys.stdin.readline

n = factorial(int(input()))
n = str(n)

count = 0
for i in range(len(n)-1, -1, -1):
  if n[i] == '0':
    count += 1
  else:
    break

print(count)

인수분해를 이용한 풀이

임의의 수 N을 인수분해해보면, 5가 곱해질 때 마다 0의 개수가 하나씩 늘어난다는 것을 알 수 있다.
N의 범위는 0부터 500사이이므로 5, 25, 125가 곱해질 때 0이 늘어난다.

Python 코드

import sys
input = sys.stdin.readline

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