백준 2004번 파이썬 문제풀이(조합 0의 개수)

---

위 문제 문과생에겐 너무 어려운 문제이다.... 해설을 보니 nCm 은 n!/m!*(n-m)! 과 같다고 한다. 여기서 생각할 수 있는 점은 어떤수의 0의 개수는 10^k * n 이라고 할 수 있다. 예를 들어 0이 5개이면 10^5 * n 이라고 할 수 있다. 여기서 10은 다시 (2*5)^5 로 나눌 수 있는데 이는 즉, 2와5의 짝이 5개 있다는 말이다. 따라서 n!/m!*(n-m)! 식에서 n! 의 2와 5의 승수를 구하고 m!,(n-m)!의 승수를 구해서 빼주면 된다. 여기서 빼는 이유는 승수의 나눗셈 계산은 빼기이기 때문이다. 그리고 짝을 찾아서 짝의 개수만큼 출력해주면 된다.

 

# 5의 승수 구하기
def five_power_n(N):
    count_5_1 = 0
    X = 5
    while X <= N:
        count_5_1 += N // X
        X *= 5
    return count_5_1


# 2의 승수 구하기
def tow_power_n(N):
    count_2_1 = 0
    X = 2
    while X <= N:
        count_2_1 += N // X
        X *= 2
    return count_2_1


N, M = map(int, input().split())

# 각각의 승수 구하기( n!/m!*(n-m)! ) 이기 때문에 승수 나누기는 빼기와 같다.
count_5 = five_power_n(N) - five_power_n(N - M) - five_power_n(M)
count_2 = tow_power_n(N) - tow_power_n(N - M) - tow_power_n(M)

print(min(count_5, count_2)) #2와 5의 짝 개수 찾기