백준 2004번 조합 0개의 개수 - python

처음 해당 문제를 봤을 때 팩토리얼을 활용하여 문제를 풀어도 되지만 시간초과가 날 것 같다는 생각이 들었다. 그러나 정말 그런지 궁금하니 한번 돌려보자..

from math import factorial

n, k = map(int, input().split())
number = factorial(n) // (factorial(k) * factorial(n - k))
i = 0
while True:
    if not number % (10 ** i):
        i += 1
    else:
        print(i - 1)
        break

해당 코드로 실행하니 당연하게 시가 초과가 발생했다. 이를 해결하기 위해 다른 방법에 대해 고민을 해 본 결과, m과 n-m의 최소값 만큼 반복문을 실행하는 방식을 진행해 보았다.

n, k = map(int, input().split())
child, parent = 1, 1
for idx in range(min(k, n - k)):
    child *= (n - idx)
    parent *= (idx + 1)
number = child // parent
i = 0
while not number % (10 ** i):
    i += 1
print(i - 1)

해당 코드인데 당연하게 시간초과가 발생

아마 경우의 수가 20억이라 n = 2000000000, m = 1000000000의 경우 시간초과 일것이다.

이후에는 다른 방법이 안떠올라 고민하던 끝에 리스트를 활용하여 풀이를 진행하면 되겠다는 생각에

def binary(n, k):
    a, b = [1] + [0] * k, [0] * (k + 1)
    for i in range(n + 1):
        for j in range(min(i, k) + 1):
            if not j or j == i:
                b[j] = 1
            else:
                b[j] = a[j - 1] + a[j]
        a = b[:]
    del a
    return b[k]


n, m = map(int, input().split())
k = binary(n, m)
i = 1
while True:
    if not k % i:
        i += 1
    else:
        print(i - 1)
        break

코드로 진행 했지만 이번에는 메모리 초과가 발생했다..이제 더이상 내 머리로는 이 문제의 좋은 방식이 떠오르지 않아 블로그를 찾아보니 2의 개수와 5의 개수를 활용하여 문제를 풀라는 블로그를 보게 되었다.

해당 문제의 경우, https://insight-bgh.tistory.com/337 의 블로그를 참고 했습니다.

나중에 다시 한 번 보면서 이해를 하는 방향으로 해야 될 것 같습니다.

def CountNum(n, k):
    answer = 0
    div = k
    while div <= n:
        answer += n // div
        div *= k
    return answer



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

five_count = CountNum(n, 5) - CountNum(m, 5) - CountNum(n - m, 5)
two_count = CountNum(n, 2) - CountNum(m, 2) - CountNum(n - m, 2)
print(min(five_count, two_count))

이렇게 작성하니 문제가 해결되었다..

해당 풀이는 위 블로그에 가면 자세하게 볼 수 있다.