[BOJ] 2004 조합 0의 개수 (Python / 파이썬)

🧷 문제

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

조합 nCm의 끝자리 0의 개수를 출력하는 문제이다.

🛠 풀이

이 문제는 시간초과를 신경써야 하는 문제이다.

Step 1.
 이 문제를 단순히 nCr = n! / r!(n-r)!을 계산한 후에 10으로 나눠서 계산하면 문제에서 주어진 입력의 범위때문에 시간초과가 난다.

Step 2.
 그렇다면 끝자리가 0이 나올 수 있는 경우를 생각해본다.
 끝자리가 0이 되려면 2와 5의 곱으로 이루어져야한다. 즉, 2와 5의 쌍의 갯수를 구하면 끝자리 0의 개수를 구할 수 있다.

Step 3.
 다시 한번, 10이 만들어지려면 2와 5가 쌍을 이뤄야 하므로 2의 갯수와 5의 갯수 중 더 작은 것을 선택하면 된다.

🖊 나의 코드

import sys
 
input = sys.stdin.readline
 
def count_two(x):
    cnt = 0
    while x > 0:
        x = x // 2
        cnt += x
 
    return cnt
 
def count_five(x):
    cnt = 0
    while x > 0:
        x = x // 5
        cnt += x
 
    return cnt
 
def count_zero(x, y):
    t = count_two(x) - count_two(y) - count_two(x-y)
    f = count_five(x) - count_five(y) - count_five(x-y)
 
    return min(t, f)
 
 
if __name__ == "__main__":
    n, m = map(int, input().split())
 
    print(count_zero(n, m))