[알고리즘 문제] Combinationzero (Python / 파이썬)

문제

n명의 사람중 m명을 순서에 상관없이 뽑는 경우의 수를 조합이라고 하며 nCm으로 나타낸다.
nCm은 수식으로 n!/m!(n-m)! 으로 구할 수 있다. (5! = 1 * 2 * 3 * 4 * 5)
n과 m이 주어졌을때 nCm의 끝자리 0의 개수를 출력하는 프로그램을 작성하시오.  

입력

첫째 줄에 정수 n, m(0≤m≤n≤1,000,000)이 들어온다.

출력

첫째 줄에 0의 개수를 출력한다.

---

문제 풀이 

처음에는 이 문제를 파스칼의 삼각형을 이용하여

해결하려고 했으나 메모리 초과 문제가 발생하였습니다. 

따라서, 다른 방법을 이용해 풀이해보았습니다. 

만약 어떤 수의 끝자리가 0이 되려면 2와 5가 있어야 합니다. 

즉, 2와 5가 짝을 이루어 끝자리가 0이 되도록 만듭니다. 

따라서 조합을 구하는 공식에서 각 경우의 2와 5의 개수를 구해주어야 합니다.

n!에서 2의 개수를 구하고 (n-r)! 과 r! 에서 구한 2의 개수를 빼줍니다. (약분하므로)

5의 개수도 2의 개수와 같은 방법으로 구해줍니다.

여기서 중요한 점은 구한 2의 개수와 5의 개수 중 더 작은 값을 출력해야 한다는 것입니다.

끝자리 0은 2와 5의 짝으로 결정됩니다. 따라서 만약 2가 2개 5가 3개 일 때 

2와 5의 짝은 2개 즉, 더 작은 개수에 의해 결정됩니다.

---

My Code

def count_two(n):
    count = 0
    while n != 0:
        n = n // 2 # 2를 계속 나눠주면서 
        count += n # 개수 계산
    return count 

def count_five(n):
    count = 0 
    while n != 0:
        n = n // 5 # 5를 계속 나눠주면서 
        count += n # 개수 계산 
    return count 

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

# 2와 5의 개수 중 더 작은 값 출력
print(min(count_two(n) - count_two(n - m) - count_two(m), count_five(n) - count_five(n - m) - count_five(m)))