[Baekjoon] 2004/조합 0의 개수/Python/파이썬/수학

💡문제

nCr의 끝자리 0의 개수를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 정수 n,m(0<=m<=n<=2,000,000,000,n != 0)이 들어온다.

출력

첫째 줄에 nCr의 끝자리 0의 개수를 출력한다.

예제입력

25 12

예제출력

2

---

📖내가 실패한 Code

import sys


def zero_counter(n, r):
    result = [0,0]
    for m in range(n, n-r-1, -1):
        while not m % 2 or not m % 5:
            if not m % 2:
                result[0] += 1
                m /= 2
            else:
                result[1] += 1
                m /= 5

    for m in range(1, r+1):
        while not m % 2 or not m % 5:
            if not m % 2:
                result[0] -= 1
                m /= 2
            else:
                result[1] -= 1
                m /= 5
    return min(result[0], result[1])


def main():
    n, m = map(int, sys.stdin.readline().split())
    print(max(zero_counter(n, m), 0))


if __name__ == '__main__':
    main()

---

📖내가 작성한 Code

import sys


def zero_counter(dividend, divisor):
    counter = 0
    while dividend != 0:
        dividend = dividend // divisor
        counter += dividend

    return counter


def make_ten(n, m):
    return min(zero_counter(n, 2) - zero_counter(n - m, 2) - zero_counter(m, 2), zero_counter(n, 5) - zero_counter(n - m, 5) - zero_counter(m, 5))


def main():
    n, m = map(int, sys.stdin.readline().split())
    print(max(0, make_ten(n, m)))


if __name__ == '__main__':
    main()

---

✍️풀이과정

처음 생각 했던 풀이 과정은,

1. 전체에서 2와 5 인수의 최솟값을 찾는다.

였지만,

시간 초과.

당연한 이야기 였지만, 20억짜리를 반복문 자체를 돈다는 것은 어불성설이었음.

하지만, 아이디어는 맞다고 생각하여 다시 설계해봄

1. 1~10까지 나열한 다음 개수의 패턴을 파악한다.
2. 0이 될때까지 나누고 그 나눈 값을 모두 더하니 개수가 나온다

다행히 통과

---

🧠 코드 리뷰

가독성과 디버깅 편의 성을 위한 변수 저장 방식 채택 희망

---

🛠️AI 개선 코드

import sys

def count_factor_in_factorial(n, factor):
    """
    n!에서 factor(주로 소수 2나 5)가 몇 번 등장하는지 반환한다.
    예) count_factor_in_factorial(10, 5) -> 2
       (10! = 3628800, 여기엔 5가 총 2번 등장)
    """
    count = 0
    while n > 0:
        n //= factor
        count += n
    return count

def trailing_zero_in_binomial(n, m):
    """
    조합 nCm의 뒤에서부터 0이 몇 개 연속으로 나오는지 계산한다.
    예) trailing_zero_in_binomial(5, 2) -> 1 
       (C(5,2) = 10, 끝의 0 개수 = 1)
    """
    # 혹시 m > n 이라면 C(n, m)는 0이므로 trailing zero도 0
    if m > n:
        return 0
    
    # v2(n!) - v2((n-m)!) - v2(m!)
    n2 = count_factor_in_factorial(n, 2)
    nm2 = count_factor_in_factorial(n - m, 2)
    m2 = count_factor_in_factorial(m, 2)

    # v5(n!) - v5((n-m)!) - v5(m!)
    n5 = count_factor_in_factorial(n, 5)
    nm5 = count_factor_in_factorial(n - m, 5)
    m5 = count_factor_in_factorial(m, 5)

    # trailing zero = min(2의 지수, 5의 지수)
    exponent_2 = n2 - nm2 - m2
    exponent_5 = n5 - nm5 - m5

    return min(exponent_2, exponent_5)

def main():
    # 입력
    n, m = map(int, sys.stdin.readline().split())
    # 결과 출력
    print(trailing_zero_in_binomial(n, m))

if __name__ == '__main__':
    main()

---

💻결과

백준문제 보러가기

---

🖱️참고 링크

팩토리얼(Factorial)의 소인수