백준 22.03.23. 2004번 - 조합 0의 개수

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


def FindTwoMultiple(a):
    t = 0
    while a >= 2:
        t += a//2
        a //= 2
    return t


def FindFiveMultiple(a):
    f = 0
    while a >= 5:
        f += a//5
        a //= 5
    return f


print(min(FindTwoMultiple(n)-FindTwoMultiple(m)-FindTwoMultiple(n-m),
      FindFiveMultiple(n)-FindFiveMultiple(m)-FindFiveMultiple(n-m)))

이것은 nCm을 의미합니다.

 

• nCm = n! / (m! * (n-m)! )입니다.
• nCm를 소인수분해 했을 때 (2 * 5)ⁿ 을 얼마나 갖는지 알아내는 문제입니다.
• 따라서 nCm이 2와 5를 각각 몇제곱씩 갖는지 알아내야합니다.
• 이를 위해서 2의 제곱수를 찾는 FindTwoMultiple과 5의 제곱수를 찾는 FindFiveMultiple 함수들을 생성하여 사용했습니다.
• 분자는 n! 이고 분모는 m! * (n-m)! 이기때문에 2와 5의 제곱수들은 분자와 분모에서 약분될 수 있습니다.
• 따라서 분자의 제곱수 - 분모의 제곱수이므로 이에 따라 출력해줍니다.