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

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

11687번: 팩토리얼 0의 개수

1. 문제 이해

0의 개수가 m개가 되는 n!의 n을 찾는 문제

2. 문제 접근

5의 개수가 m개가 되는 팩토리얼을 찾아주면 되는 문제입니다. 그래서 처음에는 5의 배수 숫자들을 찾으면 5로 계속 나눠주면서 몇개의 5가 포함되어있는지를 찾았습니다. 하지만 이렇게 풀이를 하게 되면 시간 초과가 나게 됩니다. 

중요한 포인트는 N보다 작은 수들 중에서 5로 나눠지는 숫자의 개수를 찾는 것입니다. 이를 찾는 가장 쉬운 방법은 5로 나눠보면 알 수 있습니다. ex) 41 -> 41 // 5 = 8(5, 10, 15, 20, 25, 30, 35, 40) . 여기에 이분탐색을 통해 찾아주면 됩니다.

 

입력으로 들어오는 m에 5를 곱하여 상한선 (최소 m개의 5로 나눠지는 작은 수를 가진) 을 주고 이분 탐색을 해주면 됩니다.

5 ~ 5^12까지의 숫자로 나눠서 얻을 수 있는 몫의 합이 5의 개수가 되게 됩니다. 5 ^12까지만 해주는 이유는 5^13부터는 범위를 넘어가기 때문입니다.

 

3. 풀이

import sys, heapq
from itertools import combinations
from collections import defaultdict, deque
sys.stdin = open("input.txt", "r")
input = sys.stdin.readline

n = int(input())
isFound = False

INF = float('inf')
left, right = 1, 5 * n
ans = INF

while left <= right:
    mid = (left + right) // 2
    cnt = 0
    for i in range(1, 13):
        cnt += (mid // (5 ** i))

    if cnt >= n:
        right = mid - 1

        if cnt == n:
            ans = min(mid, ans)
    elif cnt < n:
        left = mid + 1

if ans == INF:
    print(-1)
else:
    print(ans)

4. 회고

포인트를 빨리 찾지 못해서 생각보다 고전한 문제. 특정 수보다 작은 수들 중에 m의 배수인 수의 개수를 찾으려면 m으로 나눠보면 된다는 점을 배웠다.