백준 #2004 조합 0의 개수

문제 링크

[2004 조합 0의 개수]

문제 설명

$\binom{n}{m}$의 끝자리 0의 개수를 맞추는 문제

코드

import sys
input = sys.stdin.readline


def find_2_5(x):
    num_2, num_5 = 0, 0
    i = 2
    while True:
        if x // i == 0:
            break
        num_2 += (x // i)
        i *= 2
    j = 5
    while True:
        if x // j == 0:
            break
        num_5 += (x // j)
        j *= 5
    return num_2, num_5


n, m = map(int, input().split())
k = n - m
n_2, n_5 = find_2_5(n)
m_2, m_5 = find_2_5(m)
k_2, k_5 = find_2_5(k)

n_2 -= (m_2 + k_2)
n_5 -= (m_5 + k_5)
if n_2 == 0 or n_5 == 0:
    print(0)
else:
    print(min(n_2, n_5))

풀이

$n$의 범위가 무려 20억까지 해당되기 때문에 팩토리얼을 일일히 계산해서 풀 수는 없는 문제이다. 0의 개수는 2와 5의 개수에 영향을 받으니깐 분자 분모에서 2와 5의 개수를 찾아서 비교해 풀면 된다. $n!$의 2 또는 5의 개수를 구하는 방법은 2 또는 5의 지수를 1씩 더해가면서 나눠서 세어주면 된다. 화이팅!