Baekjoon Online Judge 2004번 파이썬

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

2004번: 조합 0의 개수

n과 m의 수 범위가 굉장히 크기 때문에, 이전에 팩토리얼 0의 개수 문제를 풀 때 썼던 방법을 그대로 쓰면 시간 초과가 났다.
그래서 다른 방법을 찾아보았다.
조합은 ‘n! / (n-m)!*m!‘ 이다. 여기서 생기는 2와 5의 개수를 통해 뒷자리에 생기는 0의 개수를 구해야한다.
조합 공식을 참고해서, ‘n!의 2의 개수 - (n-m)!의 2의 개수 - m!의 2의 개수' 를 이용하여 2의 개수를 구해야한다.
5의 개수도 마찬가지다.

count += N을 하는 이유는 N이 25일 때, 25 // 2, 25 // 4, 25 // 8, 25 // 16을 모두 고려해서 더해주어야하기 때문이다.

from math에 factorial()이 있다.

정답 코드

import sys

n, m = map(int,sys.stdin.readline().split())

def count(N, num):
  count = 0
  if N < num:
    return 0
  else:
    while N != 0:
      N //= num
      count += N
    return count

count_two = count(n,2) - count(n-m,2) - count(m,2)
count_five = count(n,5) - count(n-m,5) - count(m,5)

print(min(count_two,count_five))