[Python/파이썬] 백준 11687번 팩토리얼 0의 개수

11687번: 팩토리얼 0의 개수

 

코드

m = int(input())


def count_zero(n):  # 왼쪽 끝 0 개수 구하기
    res = 0
    while n >= 5:
        res += n//5
        n //= 5
    return res


s, e = 0, int(1e9)
ans = -1
while s <= e:
    mid = (s+e)//2
    zero = count_zero(mid)
    if zero == m:
        ans = mid
        e = mid-1
    elif zero < m:
        s = mid+1
    else:
        e = mid-1
print(ans)

 

가장 끝의 0이 하나 더 더해지려면 그 수에 10이 곱해지는 방법밖에 없다. 그러므로 n!일때 10이 곱해진 횟수를 구하면 되는데 생각해보면 2보다 더 큰 수인 5가 더 드물게 나오므로 결국 5가 몇 번 곱해졌는지만 구하면 된다.