[백준] 2004번: 조합 0의 개수 - [Python/파이썬]

문제

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

2004번: 조합 0의 개수

코드

#팩토리얼로 푸면 메모리제한
#10의 배수를 잘 활용 (2개수, 5개수중 적은것이 10의 개수)
import sys
def countnum(N, num):
    count=0
    div=num
    while(N>=div):
        count += (N//div)
        div*=num
    return count

n,m=map(int, sys.stdin.readline().split())
print(min(countnum(n,5)-countnum(m,5)-countnum(n-m,5),countnum(n,2)-countnum(m,2)-countnum(n-m,2)))

문제 해결

팩토리얼로 조합을 일일히 구하면 메모리 제한이 걸려서

10의 배수가 2와 5의 배수임을 이용해서 2와 5의 개수중 적은 것이 10의 개수라고 이용하여 코드를 작성했다.