[백준] 1676 팩토리얼 0의 개수 (Baekjoon Problem 1676: Count trailing 0's in factorial n)

문제 출처

 

[문제 요약]

입력을 n을 받는다. 그러면 n!에서 0 이외의 다른 수가 나오기 전까지의 0의 개수 (오른쪽 끝에 있는 0의 개수) 를 출력으로 내보내면 된다.

 

[풀이]

1부터 n까지 곱할때 나오는 2와 5의 개수를 세서 10이 몇개인지 알아내면 된다.

2*5가 10이니 2가 나온 갯수, 5가 나온 갯수중 작은 수를 돌려주면 된다.

 

[유의할점]

100같은 수는 10이 두번 곱해진 형태이다. 이처럼 어떤수의 최대공약수가 2^x * 5^y인 경우 (2 혹은 5의 몇승인 경우) 1번만 세는게 아니라 x와 y개만큼 전부 세어주어야한다.

 

[파이썬 3 코드]

def mul5(n):
    num5 = 0
    while n % 5 == 0:
        n = n // 5
        num5 += 1
    return num5


def mul2(n):
    num2 = 0
    while n % 2 == 0:
        n = n // 2
        num2 += 1
    return num2

def count0(n):
    num2 = 0
    num5 = 0
    for i in range(1, n + 1):
        if i % 5 == 0:
            num5 += mul5(i)
        if i % 2 == 0:
            num2 += mul2(i)
    return min(num2, num5)


if __name__ == "__main__":
    n = int(input())
    num0 = count0(n)
    print(num0)