[백준] 2004번 조합 0의 개수 ★

💡문제접근

• factorial값을 직접 계산하거나 아니면 factorial값을 DP에 저장한 다음 2와 5의 개수를 찾아서 둘 중 최솟값을 찾는 방식으로 접근했으나 메모리 초과가 발생했다. 왜냐하면 n, m의 범위가 0 ≤ n, m ≤ 2,000,000,000(n ≠ 0)이므로 20억의 값이 들어간다면 엄청난 시간과 메모리가 소요된다. 따라서, 이 문제는 값을 계산하지 않고 2와 5의 개수 중 최솟값을 출력해야한다.
• 문제를 풀기 위한 방법을 떠올리지 못해서 구글링해서 찾아봤다.
• 테스트케이스로 나왔던 25!을 계산하지 않고 25로 계산하고 마찬가지로 12!, 13!을 계산하지 않고 12, 13으로 계산하여 2와 5의 카운팅 값을 구한다.

💡코드(메모리 : 30616KB, 시간 : 44ms)

import sys
input = sys.stdin.readline

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

def solution(n, k):
    cnt = 0
    while n > 1:
        n //= k
        cnt += n
    return cnt

cnt_5 = solution(n, 5) - solution(m, 5) - solution(n-m, 5)
cnt_2 = solution(n, 2) - solution(m, 2) - solution(n-m, 2)
print(min(cnt_2, cnt_5))

💡소요시간 : 20m