[BOJ] 2004번 - 조합 0의 개수

---

문제설명

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

2004번: 조합 0의 개수

사고과정

• 주어진 데이터 범위가 20억이기 때문에 매우 큰 수다. 따라서 조합을 다 계산하는 것이 아닌 0의 개수만을 찾아야 함. 0개수는 2와 5의 개수로 알아낼 수 있다. 자세한 설명은 여기를 참고하자.

풀이(스스로 못 푼 풀이)

import sys

input = sys.stdin.readline
n, k = map(int, input().split())  # (n, k)

def count(n, num):
    cnt = 0
    divnum = num
    while n >= divnum:
        cnt += (n // divnum)
        divnum *= num
    return cnt

two_cnt = count(n, 2) - count(k, 2) - count(n-k, 2)
five_cnt = count(n, 5) - count(k, 5) - count(n-k, 5)

print(min(two_cnt, five_cnt))