[백준] #11687 - 팩토리얼 0의 개수 (Python)

 

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

11687번: 팩토리얼 0의 개수

 

접근법

팩토리얼 오른쪽 0의 개수를 세는 방법

1. 무작정 세기

팩토리얼 값을 구한 뒤, 문자열로 바꿔서 뒤부터 '0'을 카운트하는 방법

가장 직관적이지만, 일단 팩토리얼 값을 계산해야해서 값이 커지면 연산 횟수가 기하급수적으로 증가함

 

무작정 세는 방법으로 구현한 코드(파이썬)

import math


def find_right_zeros(n):
    digit = str(n)
    zero_count = 0
    for i in range(len(digit), 0, -1):
        if digit[i-1] == '0':
            zero_count += 1
        else:
            break
    return zero_count


fac_list = [math.factorial(i) for i in range(1, 10**2)]

m = int(input())
result = 0
start, end = 0, len(fac_list) - 1
while start <= end:
    mid = (start + end) // 2

    zero_count = find_right_zeros(fac_list[mid])

    if zero_count < m:
        start = mid + 1
    else:
        end = mid - 1
        result = mid

if find_right_zeros(fac_list[result]) != m:
    print(-1)
else:
    print(result+1)

문제점 : fac_list에 결국에 값을 비교할 팩토리얼 값을 넣어야 하는데, 10,000만 넘어가도 시간이 오래걸린다.

(당연히 정답도 아니다)

 

2. 정수론적 원리 이용하기

소인수분해 성질에 의해 다음이 성립한다.

N! 오른쪽 0의 개수 ≡ N을 5로 나눈 몫

 

증명 :

N!의 오른쪽 0의 개수 ≡ N!의 인수 중 10의 배수의 개수

≡ 2 * 5의 배수의 개수

≡ 소인수 2와 5의 배수의 개수

≡ 소인수 5의 배수의 개수

 

즉, N!의 0의 개수 ≡ 1~N!까지 5의 배수의 개수(≡ 소인수 5의 배수의 개수)

 

예로 18! = 18 * 17 * 16 * 15 * ... * 1 중 5의 배수는 15, 10, 5로 총 3개

≡ 18을 5로 나눈 몫 3

 

일반화 해서

N!의 5의 배수의 개수 ≡ N을 5로 나눈 몫

 

따라서,

 

N!의 오른쪽 0의 개수 ≡ N을 5로 나눈 몫

 

 

 

제한시간이 매우 짧으니까, 이분 탐색으로 m값을 찾으면 된다.

 

정답 코드(파이썬)

def find_right_zeros(n):
    zeros = 0
    while n >= 5:
        zeros += n // 5
        n //= 5
    return zeros


m = int(input())
left, right, result = 1, m * 5, 0

while left <= right:
    mid = (left + right) // 2

    # 메인 로직
    zero_count = find_right_zeros(mid)

    # 조건 분기
    if zero_count < m:
        left = mid + 1
    else:
        right = mid - 1
        result = mid

print(result if find_right_zeros(result) == m else -1)

 

여담

이 문제는 이분 탐색을 극적으로 활용하기보다는, "0의 개수를 어떻게 효율적으로 찾을 것인가"가 핵심인 문제다.