1. 문제

출처: 백준 2004번 조합 0의 개수

2. 풀이

$_nC_m = \frac{n!}{m!(n-m)!}$ 로 주어진다.

이때 끝자리 0의 개수의 의미는 결국 10이 몇 번 곱해졌는 지로 생각할 수 있다.
10은 2와 5가 몇 번 곱해지를 구해서, 더 적게 곱해진 숫자만큼 10이 곱해진 것이라고 볼 수 있다.

각 숫자를 2나 5로 나누면, 몫을 통해 그 숫자까지 2나 5가 한 번씩 포함된 개수가 얼마인지 알 수 있다. 이때, 제곱들은 고려가 안 되기 때문에 2나 5의 제곱들도 반복해서 나눠가며 그 몫을 구해 더해줘야 한다.

$n$에 포함된 2와 5의 개수는 10을 만드는 데 기여하고, $m$과 $n-m$에 포함된 숫자의 개수들은 오히려 10을 적게 만든다.

따라서, $n$에서 구한 개수에서 다른 두 개의 개수들을 빼주고, 2와 5의 개수 중 작은 값을 취하면 끝자리 0의 개수를 알 수 있다.

3. 소스코드

n,m=map(int,input().split())
k = n-m
t = 1
num_n, num_m, num_k = 0, 0, 0

while 5**t<=n:
    num_n += n//5**t
    if 5**t<=m:
        num_m += m//5**t
    if 5**t<=k:
        num_k += k//5**t
    t+=1

t=1
num_n2, num_m2, num_k2 = 0, 0, 0
while 2**t<=n:
    num_n2 += n//2**t
    if 2**t<=m:
        num_m2 += m//2**t
    if 2**t<=k:
        num_k2 += k//2**t
    t+=1


temp = num_n - num_m - num_k
temp2 = num_n2 - num_m2 - num_k2
temp3 = min([temp,temp2])

if temp3 > 0:
    print(temp3)
else:
    print(0)

4. 그 외

재밌게 머리 쓰면서 풀 수 있는 문제라고 느껴졌던 문제였다.