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

문제 요약

nCm의 끝자리 0의 개수를 출력하면 된다. 예를들어 n = 25, m = 12일 경우 nCm = 5,200,300 이므로, 답은 2가 된다.

접근

단순히 math.comb()와 같은 함수를 이용하면 시간초과가 발생한다. n, m의 최댓값이 20억이기 때문이다.

때문에 0의 개수는 2*5의 개수와 같다는 것을 이용해야한다.

2의 개수, 5의 개수 세기

def cnt_2(num):
    cnt = 0
    while num > 1:
        num = num // 2
        cnt += num
    return cnt

원리는 다음과 같다. 예를 들어 주어진 수가 14일 경우 14!은 다음과 같이 나타난다.

14 = 2 * 7 13 12 = 2 * 2 * 3 11 10 = 2 * 5 9 = 3 * 3 8 = 2 * 2 * 2 7 6 = 2 * 3 5 4 = 2 * 2 3 2 1

여기서 2를 포함한 수의 개수는 14 // 2와 동일한 7개임을 알 수 있다. 2를 포함한 수를 모두 2로 나누었다고 가정했을 때 다음과 같이 나타난다.

7 6 = 2 * 3 5 4 = 2 * 2 3 2 1

마찬가지로 2를 포함한 수의 개수는 7 // 2와 동일한 3개이다. 한 번 더 2로 나누면 2를 포함한 수의 개수는 2 // 2와 동일한 1개가 되고 이후로는 존재하지 않는다(1 // 2 = 0).

5에 대해서도 동일하게 적용된다. 14!에서 5를 포함한 수는 5, 10이므로, 14 // 5와 동일한 2개이며, 한 번 더 5로 나눌 경우 더이상 존재하지 않는다(2 // 5 = 0).

즉 각각 2, 5의 개수를 세는 함수를 만들어 2와 5의 개수를 셀 수 있다.

nCm의 계산식은 n! / (n-m)! * m! 이므로

[nCm의 2 개수] = [n의 2 개수] - [(n-m)의 2 개수] - [m의 2 개수] 이다.

마지막으로 답은 2 * 5의 개수이므로, 2의 개수와 5의 개수 중 작은 값이 답이 된다.

코드

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

def cnt_2(num):
    cnt = 0
    while num > 1:
        num = num // 2
        cnt += num
    return cnt

def cnt_5(num):
    cnt = 0
    while num > 1:
        num = num // 5
        cnt += num
    return cnt

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

n_2, n_5 = cnt_2(n), cnt_5(n)
m_2, m_5 = cnt_2(m), cnt_5(m)
nm_2, nm_5 = cnt_2(n-m), cnt_5(n-m)

ans_2 = n_2 - m_2 - nm_2
ans_5 = n_5 - m_5 - nm_5

print(min(ans_2, ans_5))