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

문제

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

분석

N!에서 뒤에서부터 처음 0이 아닌 숫자가 나올 때까지 0의 개수를 구하는 문제이다.

N이 최대 500이기 때문에 팩토리얼 값을 직접 구하고 문자열 연산을 통해 0의 개수를 구해도 된다.
그러나 더 효율적인 방법이 있다.
문제에서 말하는 0의 개수는 10이 곱해지는 경우에 증가한다.
즉, 어떤 수를 인수분해 했을 때 2x5(쌍)의 개수를 찾는 문제이다.
그런데 2의 개수보다 5의 개수가 더 적게 나오므로 5의 개수를 찾는 것으로 생각해도 된다. (그런데 25같은 제곱수의 경우 5가 2개이므로 추가로 세줘야한다.)

코드

해결언어 : Python

import sys
input = sys.stdin.readline

n = int(input())
cnt = 0
while n:
    cnt += n//5
    n //= 5
print(cnt)

끝으로..

수학적 사고를 요하는 문제를 많이 풀어봐야겠다.