[알고리즘][백준] 1676번 팩토리얼 0의 개수 - 파이썬(python) 풀이

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

1676번: 팩토리얼 0의 개수

---

처음에 문제를 보고 무슨 소리인가...? 솔직히 이해가 안갔다...

뭔가 살펴보니

10! = 3628800 이라 뒤에서부터 0의 개수가 2개

3! = 6이라 뒤에서부터 0의 개수가 0개

이말이었다!

import sys

n = int(sys.stdin.readline())

result = 1

cnt = 0

if n > 0:

    for i in range(1, n+1):

        result *= i

    for j in str(result)[::-1]:

        if j != '0':

            break

        else:

            cnt += 1

    print(cnt)

이렇게 짜보았는데 틀렸다고.. 

알고보니 n이 0일때를 빼버렸다...!!

 

import sys

n = int(sys.stdin.readline())

result = 1

cnt = 0

if n > 0:

    for i in range(1, n+1):

        result *= i

    for j in str(result)[::-1]:

        if j != '0':

            break

        else:

            cnt += 1

    print(cnt)

else:

    print(0)

else문에 0넣고 해피엔딩!

 

 

그런데 다른분들은 n에서 5를 나눠서 떨어지는것으로 구하시더라...

당연히 더 효율적일듯

 

5! = 1 * 2 * 3 * 4 * 5 = 120

10! = 1 * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 * 10 = 3628800 

15! =  1 * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 *10 * 11 * 12 * 13 * 14 * 15 = 1307674368000 

 

5의 개수를 찾는 문제라 n // 5 (int형태의 몫) 사용

import sys

n = int(sys.stdin.readline())

cnt = 0

while n > 1:

    cnt += n // 5

    n //= 5

print(cnt)

 

더 간편하게는

import sys

n = int(sys.stdin.readline())

 

print(n/5 + n//25 + n//125)

 

25와 125로 더 나누는 이유는

25 = 5 * 5 -> 5가 2개

125 = 5 * 5 * 5 -> 5가 3개라 그런것이고

625가 없는 이유는 input으로 500까지만 받기때문!

 

좀 더 효율적으로.. 생각하는 습관을 들여야겠다