[파이썬] 2004번. 조합 0의 개수 풀이

먼저 문제의 입력이 20억까지이므로 그냥 조합을 직접 계산하면 시간초과, 메모리 초과 가 난다.

 

끝자리가 0이라는 것은 2와 5의 곱으로 이루어져 있다는 것이다.

예를 들어 10 = 2 x 5이다.

나아가 끝자리 0이 2개라면, 2와 5의 곱이 2쌍이라는 것이다.

즉, 100 = 2 x 2 x 5 x 5이다.

 

따라서 "어떤 수의 끝자리 0의 개수는 그 수의 인수 2와 5의 개수 중에서 최소값이다." 라는 사실을 가지고 문제를 풀면 된다.

 

문제는 조합의 0의 개수니까 == N! 의 인수 2와 5의 개수 - ( (N - M)!의 인수 2와 5의 개수 + M!의 인수 2와 5의 개수)의 최소값을 찾으면 된다.

 

def count_two(n):
    count = 0
    i = 2
    divisor = 2
    while (divisor <= n):
        count += n // divisor # n이 2, 4, 8 ... 의 배수인지 확인하여 2를 인수로 몇개 가지고 있는 지 확인한다.
        divisor = 2 ** i
        i += 1

    return count

def count_five(n):
    count = 0
    i = 2
    divisor = 5
    while (divisor <= n):
        count += n // divisor # n이 5, 25, 125 ... 의 배수인지 확인하여 5를 인수로 몇개 가지고 있는 지 확인한다.
        divisor = 5 ** i
        i += 1

    return count

그렇다면 각 팩토리얼을 직접 계산하여 인수분해를 해서 인수를 찾아야 할까? 아니다.

예를 들어, 8! = 8 7 6 5 4 3 2 1 에서는 2가 나오는 횟수가 7번이다.

왜냐하면 각각

8 = 2x2x2

6 = 2x3

4 = 2x2

2 = 2x1 이므로 2가 7번 나오는 것을 알 수 있다.

 

여기서 알 수 있는 것은 먼저 8 7 6 5 4 3 2 1에서 2의 배수의 개수를 구한다. 8 // 2 = 4개

다음으로 2의 제곱수에 대해서 배수를 구한다. 8 // (2*2) = 2개

다음으로 2의 세제곱수에 대해서 배수를 구한다. 8 // (2*2*2) = 1개

신기하게도, 이렇게 하면 4 + 2 + 1 = 7번이라는 횟수를 도출할 수 있다.

 

100! 을 예를 들어도 과정은 동일하다. 이번에는 인수가 5일 때를 구해보자.

일단 100까지의 수 중에서 5의 배수들이 5를 1개씩 인수로 가지고 있다. -> 100 // 5 = 20개

그 다음 5의 제곱수인 25의 배수들은 5를 하나씩 더 가지고 있다. (2개 이상) -> 100 // 25 = 4개

그 다음 5의 세제곱수인 125의 배수는 없으므로, 100! 의 인수 5의 개수는 24개가 된다.

 

N, M = map(int, input().split())

N_two , N_five = count_two(N), count_five(N)
NM_two, NM_five, M_two, M_five = count_two(N-M), count_five(N-M), count_two(M), count_five(M)

# 분자에서 분모의 인수 2, 5의 개수를 빼고, 그 중 최소값이 문제의 정답이다.
print(min((N_two-NM_two-M_two), (N_five-NM_five-M_five)))

 

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

2004번: 조합 0의 개수