백준 알고리즘 2004번 조합 0의 개수(python)

조합 문제이다.

단순히 조합을 계산하고 뒤에 0의 개수를 새면 시간 초과가 걸리기 때문에 효율적인 방법을 찾아야 된다.

아래의 코드가 처음에는 이해가 잘 안될수도 있다. 예시를 들어 풀다 보면 이해가 더 잘 될 것이다.

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

def cnt2(n):
    n2 = 0
    while(n != 0):
        n //= 2
        n2 += n
    return n2

def cnt5(n):
    n5 = 0
    while(n != 0):
        n //= 5
        n5 += n
    return n5

print(min(cnt2(n)-cnt2(m)-cnt2(n-m), cnt5(n)-cnt5(m)-cnt5(n-m)))