[백준] 조합 0의 개수

2004번: 조합 0의 개수

🔗 문제

입력

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

25 12

출력

2

💡풀이 방법 → 참고

• 팩토리얼을 직접 구하거나 math.factorial()를 사용해서 팩토리얼을 구하면 시간 초과가 발생했다.
• math.comb()를 사용해서 조합 자체를 구하는 방법 또한 시간초과가 발생했다.
• 0의 개수를 구한다는 것은 10이 곱해진 형태를 말한다.
• 10은 2와 5를 곱했을 때 만들어진다. $x × 10^k = 2^n × 5^m$(n, m 중 작은 수가 k가 된다.) 2와 5의 짝이 맞을 때 10이 만들어지기 때문에 이를 생각해서 함수를 만들면 된다.
  

💻 코드

# 시간초과(python, pypy) - 팩토리얼과 조합 모두 구하면 발생
n, m = map(int, input().split())
result = 0 

def Factorial(lastNumber):
    factorial = 1
    for i in range(1, lastNumber+1):
        factorial *= i
    return factorial

temp = Factorial(n) // (Factorial(m) * Factorial(n-m))

while True:
    if temp % 10 == 0:
        result += 1
    else:
        break
    temp = temp // 10
print(result)

# [1676] 팩토리얼 0의 개수
def checkNumber(number, base):
    result = 0 
    while number:
        number = number // base 
        result += number
    return result 

n, m = map(int, input().split())
baseFive = checkNumber(n, 5) - checkNumber(m, 5) - checkNumber(n-m, 5)
baseTwo = checkNumber(n, 2) - checkNumber(m, 2) - checkNumber(n-m, 2)

print(min(baseFive, baseTwo))