[백준 2004번] 조합 0의 개수 in python

문제

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

입력

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

출력

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

 

예제 입력 1

25 12

예제 출력 1

2

---

이전에 https://lucian-blog.tistory.com/84 팩토리얼 0의 개수를 구하는 문제를 풀었다.

 

이것도 비슷하면서 조금은 다른 문제이다.

 

우선 조합식을 보자. 

$_{n}C_{r}=\frac{n!}{(n-m)!r!}$

 

이제 예제를 봐야한다.

n=10, m=5로 놓는다.

그러면 $_{10}C_{5}=\frac{10!}{(10-5)!5!} = \frac{3628800}{(120)*120}$이 된다.

10!=3628800

5!=120

 

이를 소인수분해해보자.

$\frac{3628800}{(120)*120}=\frac{5^{2}*2^{8}*3^{4}*7}{(5^{1}*2^{3}*3)*(5^{1}*2^{3}*3)}$

즉 0의 갯수는 2의 지수와 5의 지수 중 작은 값이 결정된다. (미심쩍다 싶으면 250을 소인수분해 해보자!)

10!은 5의 지수가 2이고 2의 지수가 8이므로 5의 지수인 2가 0의 갯수가 된다.

5!은 5의 지수가 1이고, 2의 지수가 3이므로 5의 지수인 1이 된다.

또한 식의 *와 /는 지수에선 +와 -로 표현이 가능하므로, 이것을 표현하면

5의 지수에선 $5^{2-1-1}$, 2의 지수에선 $2^{8-3-3}$이므로 

5의 지수=0, 2의 지수=2가 된다.

즉 $5^{0}*2^{2}*3^{2}*7$이 된다.

그러면 5의 지수인 0이 최소이므로 0의 갯수또한 0개가 된다.

 

이것을 코드화하면,

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

def factorial_5or2_cnt(num,t):
  cnt=0
  while num>0:
    cnt+=num//t
    num//=t
  return cnt

cnt_5=factorial_5or2_cnt(n,5)-factorial_5or2_cnt(m,5)-factorial_5or2_cnt(n-m,5)
cnt_2=factorial_5or2_cnt(n,2)-factorial_5or2_cnt(m,2)-factorial_5or2_cnt(n-m,2)
result=min(cnt_5,cnt_2)
print(result)

5의 지수에서 계산을 하고, 2의 지수에서 계산을 하고

그것은 min함수로 가장 작은 값을 뽑아낸 코드이다.(코드가 이해가 안되면 팩토리얼에서 0의 개수구하는 이전 글을 보면 된다~)