[파이썬] 백준 2004번 조합 0의 개수

2004번: 조합 0의 개수

시간 제한

 2초

메모리 제한

128MB

문제

 $n \choose m$의 끝자리 0의 개수를 출력하는 프로그램을 작성하시오.

입력

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

출력

첫째 줄에 $n \choose m$의 끝자리 0의 개수를 출력한다.

예제 입력 1 

25 12

예제 출력 1 

2

---

나의 풀이

• 숫자의 범위가 20억이기 때문에 for문을 통해서 N까지 순회하면 시간 초과가 발생한다.
• 따라서 5, 2의 인수의 개수를 몫의 성질로 빠르게 구한다.
• 팩토리얼 0의 개수에선 5의 개수만 알더라도 10의 개수를 알 수 있었지만 분모의 팩토리얼에 의해 5, 2의 개수가 달라질 경우가 있기 때문에 5, 2의 개수를 따로 구해서 계산한다.
• 실제로 5만 셀 경우 $5 \choose 4$에서 10을 만들 수 없음에도 5가 있기 때문에 1로 출력되는 문제가 발생한다.

n, m = map(int, input().split())

def count_five(n):
    count = 0
    while n != 0:
        n //= 5
        count += n
    return count

def count_two(n):
    count = 0
    while n != 0:
        n //= 2
        count += n
    return count

n_five, n_two = count_five(n), count_two(n)
m_five, m_two = count_five(m), count_two(m)
nm_five, nm_two = count_five(n-m), count_two(n-m)

total_zero = min((n_five - m_five - nm_five), (n_two - m_two - nm_two))
print(total_zero)