[🥈2 / 백준 2004 / 파이썬] 조합 0의 개수

 

2004번: 조합 0의 개수

 

문제

입력

첫째 줄에 정수 n, m (0≤m≤n≤2,000,000,000, n≠0)이 들어온다.

출력

첫째 줄에 (nm)의 끝자리 0의 개수를 출력한다.

 

예제 입력 25 12

예제 출력 2

 

 

풀이

 

직전 문제와 비슷하지만, 범위가 엄청 늘고 N! 대신 조합으로 바뀌었다.

 

이전 문제에선 범위가 작아 5씩 늘려가며 세어도 충분했다.

 

하지만 이번엔 2,000,000,000 이라는 어마어마한 숫자가 주어졌기 때문에

 

같은 방법으로 한다면 시간초과가 날 것이므로 규칙을 찾아야 한다.

 

 

N! 을 소인수분해할 때 5가 한 개 이상 포함된 수의 개수를 구하기 위해서는

 

5, 10, 15, 20, 25, … 가 포함되므로 N / 5 를 하면 된다. 

 

5가 두 개 이상 포함된 수를 구하기 위해서는 N / 5^2,

 

세 개 이상 포함된 수를 구하려면 N / 5^3, 이후 동일한 방법으로 진행하면

 

5의 총 개수를 구할 수 있다. N을 나누는 몫이 0이 될 때까지 5의 배수로 나눠주며 그 몫을 더해주자.

 

단, 단순히 N! 가 아니라 조합이기 때문에 5 뿐만 아니라 2의 개수도 신경써야한다.

 

조합 (25 16)의 5의 개수와 2의 개수를 비교한다면 5는 2개, 2는 0개가 된다.

 

당연히 2 없이는 10이 만들어질 수 없으므로 끝자리 0의 개수는 0개가 된다.

 

n, m = map(int,input().split())
f = [5**i for i in range(1,15)]
t = [2**i for i in range(1,32)]

def facZero(n,a):
    result = 0
    for i in a:
        if n // i == 0:
            return result
        result += n // i

print(min(facZero(n,f) - (facZero(n-m,f) + facZero(m,f)), facZero(n,t) - (facZero(n-m,t) + facZero(m,t))))