[Python] 백준 파이썬 2004 조합 0의 개수

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

2004번: 조합 0의 개수

• 첫 번째 풀이

# 백준 2004 조합 0의 개수

import math
import sys

n, m = map(int, sys.stdin.readline().split())
comb = list(str(math.comb(n, m)))

zero_cnt = 0
for i in range(1, len(comb)+1):
  if comb[-i] == '0':
    zero_cnt += 1
  else:
    print(zero_cnt)
    break

이 전에 푼 팩토리얼 0의 개수랑 비슷하게 풀었는데 시간 초과가 떴습니다.

• 두 번째 풀이

import sys
input = sys.stdin.readline

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

def count_2(N):
    if N < 2:
        return 0
    
    count = 0
    while N >= 2:
        count += N//2
        N = N//2
    return count

def count_5(N):
    if N < 5:
        return 0
    
    count = 0
    while N >= 5:
        count += N//5
        N //= 5
    return count

two_cnt = count_2(n) - count_2(n-m) - count_2(m)
five_cnt = count_5(n) - count_5(n-m) - count_5(m)
print(min(two_cnt, five_cnt))

$\begin{pmatrix} n  \\ m \end{pmatrix} = \frac{n!}{m! (n-m)!}$입니다.

 

분모, 분자에서 각각 2와 5의 지수를 각각 구해주고 빼주면 됩니다.

 

그리고 2와 5의 지수 중 더 작은 값으로 0의 개수가 정해지게됩니다.