[파이썬(Python)] 백준 2004번 조합 0의 개수

 

 

백준 2004번: 조합 0의 개수

문제 바로 가기

---

📌 문제

$\binom{n}{m}$의 끝자리 0의 개수를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 정수 $n, m$ $(0 \leq m \leq n \leq 2,000,000,000, n \neq 0)$이 들어온다.

출력

첫째 줄에 $\binom{n}{m}$의 끝자리 0의 개수를 출력한다.

 

 

 

📝 문제 접근 방법

문제 이해

• $\binom{n}{m}$의 끝자리에서 0의 개수를 구해야 합니다.
• 끝자리 0은 곱셈 과정에서 $10 = 2 \times 5$가 만들어질 때 발생합니다.
• 따라서 $\binom{n}{m}$의 끝자리 0의 개수를 구하려면 2와 5의 쌍의 개수를 계산해야 합니다.

 

 

조합과 팩토리얼의 관계

• 조합 $\binom{n}{m}$은 다음과 같이 정의됩니다.

$$\binom{n}{m} = \frac{n!}{m! (n-m)!}$$

• 끝자리 0의 개수는 $n!$, $m!$, $(n-m)!$에 포함된 2와 5의 개수에 의해 결정됩니다.

$$\text{Trailing Zeros in } \binom{n}{m} = \min (\text{Count of 2s, Count of 5s})$$

 

 

2와 5의 개수 계산 방법

$N!$에서 특정 소인수 $p$의 개수는 다음 공식을 사용해 계산할 수 있습니다. 

$$\text{Count of } p \text{ in }N! = \left\lfloor \frac{N}{p} \right\rfloor + \left\lfloor \frac{N}{p^2} \right\rfloor + \left\lfloor \frac{N}{p^3} \right\rfloor + \cdots $$

• 먼저 $N$을 $p$로 나눠서 $p$의 배수들이 몇 개 있는지 구합니다.
• 다음으로 $p^2$의 배수들이 몇 개 있는지도 구합니다.
• 또 $p^3, p^3, \dots$도 계속 나눠가며 계산합니다.
• 모든 결과를 더하면 $N!$에 포함된 $p$의 총 개수를 알 수 있습니다.

 

끝자리 0 개수 계산

1. $n!$의 2와 5의 개수 계산

2. $m!$과 $(n-m)!$의 2와 5의 개수 계산

3. 조합식에 따라 소거

$$\text{Count of 2s in } \binom{n}{m} = \text{Count in } n! - (\text{Count in } m! + \text{Count in } (n-m)! )$$

$$\text{Count of 5s in } \binom{n}{m} = \text{Count in } n! - (\text{Count in } m! + \text{Count in } (n-m)! )$$

4. 끝자리 0의 개수 

$$\text{Trailing Zeros in } \binom{n}{m} = \min (\text{Count of 2s, Count of 5s})$$

 

 

👩‍💻 나의 답안

🌱 깃허브

def count_factors(n, p):
    cnt = 0
    while n >= p:
        cnt += n // p
        n //= p
    return cnt

def trailing_zeros(n, m):
    if m == 0 or n == m:
        return 0
    
    cnt_2 = count_factors(n, 2) - count_factors(m, 2) - count_factors(n - m, 2)
    cnt_5 = count_factors(n, 5) - count_factors(m, 5) - count_factors(n - m, 5)

    return min(cnt_2, cnt_5)

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