[백준/Python] (S2) 조합 0의 개수 - 2004

Baekjoon Online Judge의 2004번 조합 0의 개수 문제의 Python 풀이입니다.

2004번: 조합 0의 개수

💻코드

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

def C(n, f):
    count = 0
    while n:
        n //= f
        count += n
    return count

A = C(n, 2) - C(m, 2) - C(n - m, 2)
B = C(n, 5) - C(m, 5) - C(n - m, 5)

print(min(A, B))

🧠풀이

조합의 수를 직접 계산하는 대신, 그 결과에 10이 몇 번 곱해져 있는지를 찾아야한다. 10은 2와 5의 곱이므로, nCm의 결과에 포함된 2의 개수와 5의 개수 중 더 작은 값을 찾으면, 그것이 결과의 끝자리에 있는 0의 개수가 된다.

🤔느낀 점

생각없이 math.comb 쓰다가 시간초과...