[baekjoon] 백준 1676번 : 팩토리얼 0의 개수 (by python 파이썬)

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

1676번: 팩토리얼 0의 개수

 

정답 code

import sys
input = sys.stdin.readline

n = int(input())

cnt = 0

while n>= 5:
    cnt += n//5
    n //= 5

print(cnt)

 

짧은 정답 code

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

 

이번문제는 문제를 이해하는데 어려움이 있었다.

문제가 원하는 바는 팩토리얼을한 결과값에서 뒤에서부터 0의 갯수를 세는 문제였다

 

처음엔 재귀함수로 팩토리얼을 구현한다음에 세려고 시도해보았다.

하지만 무조건 시간초과가 날것이라 생각하고 규칙을 찾아보기로했다.

 

규칙은 5로 나눈 몫 만큼의 0이 나왔는데 추가로 생각해야 될점은 5의 제곱마다 수가 추가가 된다는 것이였다.

따라서 while문속에 5로 나눈값을 먼저 저장후에 5로 나누어 5의 제곱이상인 수가 나오면 while문을 돌려주면 된다.

 

하지만 문제에서 원하는 범위가 짧기때문에 구글링을해본결과 짧은 정답 code처럼 해결할수도 있었다.