백준 2004번: 조합 0의 개수 (Python)

접근

당연히 이전 단계별 문제들에서 풀었던 것과 같이 팩토리얼을 이용한 풀이를 했지만 역시 당연하게도 숫자의 범위 때문에 메모리 초과가 떴다. 풀지 못하고 헤메다가 다른 분들 풀이의 도움을 받았다.

10은 2와 5로 이루어져있다. 어떤 수를 소인수분해 했을 때 2와 5의 개수 중 작은 값이 그 숫자의 0의 값과 일치한다..! 게다가 그 수를 2로 나누면 그 2의 개수가 한개 줄어들게 된다. 이 점을 이용하여 그 수가 가지고 있는 2의 개수와 5의 개수를 계산하여 서로 더하고 빼서 문제를 해결할 수 있다.

n!의 2 개수 및 5 개수를 세는 함수를 만들고 함수의 값끼리 더하고 뺀 후, 그 최소값을 이용하여 0의 개수를 구할 수 있다.

코드

def c_two(n):
    count = 0
    while n != 0:
        n = n // 2
        count += n
    return count


def c_five(n):
    count = 0
    while n != 0:
        n = n // 5
        count += n
    return count


a, b = map(int, input().split())
if b == 0:
    print(0)
else:
    print(min(c_two(a) - c_two(b) - c_two(a - b), c_five(a) - c_five(b) - c_five(a - b)))

더 생각해 볼 것?

...

코드나 내용 관련 조언, 부족한 점 및 질문 언제든 환영합니다!