---

백준 11687번

---

💡 문제 힌트

팩토리얼의 오른쪽 0의 개수라는 것은 해당 수가 10의 배수를 몇 개 가지고있는지를 구하는 것과 같다

예를 들어 5! = 120은 0을 1개 가지고있는 수라고 생각하면 된다

---

💡 문제 접근 방법

문제 제목이 팩토리얼이지만 팩토리얼로 접근하면 안된다

시간이 매우 짧으므로 1부터 N까지 곱하여 N!을 구하려고 하면 문제를 맞출 수 없다

수학적으로 접근해야 맞을 수 있는 문제 !

---

💡 문제 풀이

1️⃣ 소인수분해

힌트에서 이야기한 것 처럼, 오른쪽 0의 개수를 구하려면 우리는 10의 배수에 관심을 가져야한다
그러려면 소인수분해를 생각해야한다
예를들어
5! = 120 = 2^3 * 3 * 5 -> 0의 개수 1개
10! = 3628800 = 2^8 * 3^4 * 5^2 * 7 -> 0의 개수 2개
즉, 소인수 분해를 해보면 아래와 같이 정의할 수 있다

0의 개수
= 10의 배수 개수
= 2 * 5의 배수 개수
= 5의 배수 개수 (2의 배수 개수는 5의 배수보다 항상 많으므로)

2️⃣ 5의 개수 찾기

그렇다면 우리는 M!에서 소인수분해했을 때 5의 몇 제곱을 인수로 가지는가
즉, 5의 개수를 구해야한다
큰 숫자를 예시로 살펴보자

다음과 같이 127!은 1부터 127까지 곱한 숫자이다
곱한 숫자들 중 우리는 5의 배수에만 관심이 있으니 5의 배수들만 모아보자
5, 10, 15, 20, ... 110, 115, 120, 125
이 숫자들은
5*1, 5*2, 5*3, ... 5*22, 5*23, 5*24, 5*25로 표현할 수 있다
여기서 25개의 5를 찾을 수 있다 -> 25개
남은 1, 2, 3, ..., 22, 23, 24, 25에서 5의 배수는
5, 10, 15, 20, 25
5*1, 5*2, 5*3, 5*4, 5*5로 표현할 수 있으며
여기서 5개의 5를 찾을 수 있다 -> 5개
남은 1,2,3,4,5에서 5의 배수는 5 -> 1개
이런 식으로 5가 몇 개 있는지 찾을 수 있다
즉, 127!의 5의 개수는 125를 5로 나눈 몫(25), 25를 5로 나눈 몫 (5), 5를 5로 나눈 몫(1)을 모두 더한 31개이다

3️⃣ 이분탐색

2번과 같은 방식으로 0의 개수를 구하는 메서드를 구현한 다음,
가장 낮은 값과 가장 큰 값 사이를 이분탐색을 통해 반복하면서
해당 숫자의 0개수가 원하는 0의 개수와 같으면 답이 되게 코드를 구현하면 된다

---

💡 코드 구현

제출 답안 링크

# 0의 개수 구하는 메서드
def count_zero(n):
    cnt = 0
    while n >= 5:
        cnt += n // 5
        n = n // 5
    return cnt

# M : 원하는 0의 개수
M = int(input())
lower = 1
upper = M * 5
result = 100000000

while lower <= upper:
    mid = (lower + upper) // 2

    zero = count_zero(mid)

    if zero < M:		# M보다 적게나왔으면 mid값을 키운다
        lower = mid + 1
    elif zero >= M:		# M보다 크게나왔으면 mid값을 작게한다
        if zero == M:
            result = mid
        upper = mid - 1

if result == 100000000:
    print(-1)
else:
    print(result)