[Baekjoon]백준 1676 팩토리얼 0의 개수(실버 5) - Python

문제설명

문제를 살펴보면 N!을 구한 후에 뒤에서부터 0의 개수가 몇개인지 확인하면 된다

예제를 살펴보면 10! 은 3628800이기 때문에 2가 나오고, 3!은 6이기 때문에 0이 정답이다

 

팩토리얼 값을 구하는 함수를 재귀적으로 호출하는 방식으로 하나 만들어주고,

리스트를 하나 만들어서 뒷자리부터 차례대로 숫자를 하나씩 저장한다

이후에 리스트를 확인하며 0인 경우 cnt += 1을 해주고 아니라면 종료하면 된다

def factorial(num):
    if num > 1:
        return num * factorial(num - 1)
    else:
        return 1
    
N = int(input())
result = factorial(N)
digit = []
while result > 0: # 뒷자리부터 digit리스트에 저장
    num = result % 10
    digit.append(num)
    result //= 10
    
cnt = 0
i = 0
while digit[i] == 0:
    i += 1
    cnt += 1
print(cnt)

해당 코드를 제출하면 정답임을 확인할 수 있지만, 다른 분들의 코드의 길이가 상당히 짧았다

(물론 위의 코드보다 더 짧게 while문 하나로도 해결이 가능하다)

그래서 어떠한 비밀이 숨겨져있는지 확인해보니 수학적인 원리를 이용하면 훨씬 간단한 문제였다

결국 뒷자리가 0이라는 뜻은 2 * 5 가 포함되어있기때문에 가능한 숫자이다

이를 활용하면 팩토리얼보다 작은 5의 개수를 구하면 된다

제곱수도 생각을 해주어야하기 때문에 이를 반영하여 코드를 두 줄로 간단하게 작성하면

N = int(input())
print(N//5 + N//25 + N//125)

이렇게 된다 수학적 원리를 이용하면 두 줄로도 해결이 가능한 문제이다