조합 0의 개수

bookmark

n!의 뒤에 붙은 연속된 0의 개수는 n!을 소인수분해했을 때 5의 개수와 동일

나의풀이

from math import factorial

n, m = map(int, input().split())
combination = factorial(n) / ((factorial(m) * factorial(n - m)))

combination = str(int(combination))
count_0 = 0


print(count_0)

팩토리얼로 계산하려니깐 시간 초과가 나온다.

모범답안

소인수 분해를 이용해서 문제를 푼다. 10 을 나누는 경우 2 5 가 나오는데

2 5의 개수를 이용해서 0의 개수 구하기

def count_trailing_zeros(n, base):
    count = 0
    while n >= base:
        n //= base
        count += n
    return count


def count_combination_zeros(n, m):
    count_2 = (
        count_trailing_zeros(n, 2)
        - count_trailing_zeros(m, 2)
        - count_trailing_zeros(n - m, 2)
    )
    count_5 = (
        count_trailing_zeros(n, 5)
        - count_trailing_zeros(m, 5)
        - count_trailing_zeros(n - m, 5)
    )
    return min(count_2, count_5)


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

result = count_combination_zeros(n, m)
print(result)
# 25 12

2 5의 짝이 맞아야 하니깐 2,5 중의 최소값이 10의 만드는 개수이다.

count_2 = (
        count_trailing_zeros(n, 2)
        - count_trailing_zeros(m, 2)
        - count_trailing_zeros(n - m, 2)
    )

n,m사이의 조합을 구해야 하니깐 해당 식을 사용