[백준] / [Python] / [2004] 조합 0의 개수

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

2004번: 조합 0의 개수

---

문제

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

입력

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

출력

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

---

차례대로 0의 개수를 세려고 하면 오류 시간초과가 뜬다

\(\rightarrow\) 2,000,000,000 까지의 범위라서 당연한 결과이다.

def fac(n):
    answer = 1
    for i in range(1, n+1):
        answer *= i
    return answer 

def nCr(n, r):
    return fac(n) // (fac(r) * fac(n-r))

N, M = map(int, input().split())

sN = str(nCr(N, M))

answer = 0
for n in sN[::-1]:
    if n != '0':
        break    
    answer += 1
    
print(answer)

0이 생기는 경우는 곱하는 과정에서 10이 만들어지는 경우입니다. 이는 2와 5가 곱해졌을 때 만들어진다는 뜻입니다.

따라서 구해야 하는 수에 2가 몇번 나누어지는 개수, 5가 몇번 나누어지는 개수 중 더 작은 개수를 선택하면 됩니다.

# 5가 몇번 나누어지는지 
def fiveCount(n):
    answer = 0
    while n != 0:
        n = n // 5
        answer += n
    return answer

# 2가 몇번 나누어지는지
def twoCount(n):
    answer = 0
    while n != 0:
        n = n // 2
        answer += n
    return answer

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

if m == 0:
    print(0)
else:
    # 2와 5의 개수를 nCm을 구할 때처럼 구해서 더 작은 개수를 선택한다.
    print(min(twoCount(n) - twoCount(m) - twoCount(n - m), fiveCount(n) - fiveCount(m) - fiveCount(n - m)))