[백준] 2004번 조합 0의 개수 - Python / 알고리즘 기초 1/2 - 수학 1

---

---

---

💡 문제

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

입력

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

출력

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

---

💭 접근

1676번 팩토리얼 0의 개수 문제와 비슷한 문제이다.
$_nC_m$의 공식은 $\frac{n!}{m! \times (n - m)!}$ 이므로 $n!$의 소인수분해 2와 5의 개수에 $m!$과 $(n-m)!$의 소인수분해 2와 5의 개수를 뺀 값(나누기 연산으로 인해) 중 작은 값이 정답이 된다.

이때 5의 개수를 구하는 함수를 보면,

def count5(n):
    cnt = 0
    while n != 0:
        n //= 5
        cnt += n
    return cnt

n을 5로 나눈 몫이 5의 개수가 되며, 이를 n이 0이 될때까지 반복하면 5의 거듭제곱수의 개수까지 구할 수 있다.

---

📒 코드

def count5(n): # 5, 25, 125.. 의 개수를 구하는 함수
    cnt = 0
    while n != 0:
        n //= 5
        cnt += n
    return cnt

def count2(n): # 2, 4, 8, ...의 개수를 구하는 함수
    cnt = 0
    while n != 0:
        n //= 2
        cnt += n
    return cnt

n, m = map(int, input().split())
cnt_2= count2(n) - count2(m) - count2(n - m)
cnt_5= count5(n) - count5(m) - count5(n - m)

print(min(cnt_2, cnt_5))

---

💭 후기

조합을 구하는 공식과 1676번 팩토리얼 0의 개수 문제를 이해했다면 쉽게 풀릴 문제.

---

🔗 문제 출처

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

---