[Python] BOJ 2004 조합 0의 개수

출처 : 백준

 

이 문제를 풀기 전에 팩토리얼과 승수의 관계를 알아야 한다. 예를 들어 5! 을 소인수 분해하면 2의 승수는 몇일까? 

5! = 120이고

$ 2^3 \times 3 \times 5 $ 이기 때문에 3이 정답이다. 이를 컴퓨터가 계산하기 위해서 어떻게 해야 할까. 

5! = $ 1 \times 2 \times 3 \times 4 \times 5 $ 

반복문을 1부터 5까지 돌며 2로 나누어지는 수가 있으면 그 수가 1이 될 때까지 2로 나누어주고 나누어 줄 때마다 카운트를 올린다. 

 

 

하지만, 문제에서는 M과 N의 범위가 20억까지 주어지기 때문에 이 방법은 시간 초과를 유발한다. 그렇다면 이 승수를 빠르게 계산하기 위한 방법이 필요한데 이는 다음과 같다.

5! 에서 2의 승수를 보기 위해서 5/2 + 5/4 + 5/8... = 3이다. 이 공식을 풀어보면, 

5! = $ 1 \times 2 \times 3 \times 4 \times 5 $ 에서 2의 배수는 2개, 4의 배수는 1개가 나온다. 

 

만약 10! 에서 2의 승수를 구하는 경우

10! = $ 1 \times 2 \times 3 \times 4 \times 5 \times 6 \times 7 \times 8 \times 9 \times 10 $

에서 2의 배수는 5개, 4의 배수는 2개, 8의 배수는 1개 총 8개가 나오기 때문에 2의 승수는 8이다.

코드로 구현하면 다음과 같다.  

 

 

문제로 돌아와서,

 

이항 계수에서 0의 개수를 구하는 것인데 이항 계수는 $ \frac{n!}{{n-r!} \times r! } $ 이므로

분자의 0의 개수에서 분모의 0의 개수를 빼주면 된다. 

 

문제에선 0의 개수를 구하는 것인데 이는 소인수 중에 2 * 5의 한쌍이 있으면 0이 하나가 추가된다. 2 * 5 가 두 쌍이 있으면 100이 되기 때문에 0이 두 개가 붙는다. 즉 2의 승수와 5의 승수중 작은 값이 n! 의 0의 개수가 되는 것이다. 

 

그래서 이 문제는 각 팩토리얼마다 2의 승수와 5의 승수를 구하고 분자에서 분모로 그 승수를 빼주면 된다.

 

예를 들어 5C2 는 $ \frac {5!}{3! \times 2!} $이고 분자의 2의 승수는 3, 5의 승수는 1이다. 분모의 2의 승수는 2. 5의 승수는 0이다. 따라서 2의 승수끼리 빼주고 5의 승수끼리 빼주면 2의 승수는 1, 5의 승수는 1이다. 정답은 2의 승수와 5의 승수중 작은 값을 선택해야 0의 개수가 되므로 답은 1이다. 

 

이를 코드로 구현하면 다음과 같다.

def count(n,m):
    count =0
    while(n>=m):
        count += n//m
        n //= m
    return count

a,b = map(int, input().split())
son = [count(a,2), count(a,5)]
parent = [count(a-b, 2) + count(b,2) , count(a-b, 5) + count(b,5)]
total = [i-j for i, j in zip(son, parent)]
print(min(total))