백준 1676번: 팩토리얼 0의 개수 - 파이썬

백준 1676번: 팩토리얼 0의 개수 (www.acmicpc.net/problem/1676)

 

💡접근

• 시간 제한 : 2초
• 구해야 하는것은 팩토리얼 결과값의 1의 자리부터 0이 나오지 않는 첫번째 숫자까지 0의 개수를 구하는것이다.
• 단순히 팩토리얼을 다 계산한 다음에 뒤에서부터 0의 개수를 세면 되지 않을까?
• ⚠️ 일단 문제에서 가장 큰 수인 500!의 자릿수는 무려 528이다...
• ⚠️ 역시 파이썬...! Python3.0부터는 int에 사이즈가 없어져서 자료형은 int를 사용해도 될 것 같다.
  • https://docs.python.org/3/whatsnew/3.0.html#integers
• 팩토리얼을 계산한 후에 뒤에서 0의 개수를 세는 방법으로 풀겠다.

 

 

💡배운점 및 오답원인

• 다른 사람들의 풀이를 보니, Java의 경우 BigInteger를 써야하고 숫자가 크기 때문에 팩토리얼 결과값을 구하기보다는, 소인수분해로 10을 만드는 숫자인 2와 5의 짝 개수를 구하여 문제를 풀었다.
• 그 중에서도, 팩토리얼의 경우 2가 5보다 작기 때문에 5의 개수를 누적합으로 구하여 짧고 간결하게 푼 풀이가 마음에 들었다.
• (참고용) 5의 개수를 누적합으로 구하는 풀이 : https://st-lab.tistory.com/165

 

💡풀이 코드

import math

n = int(input())
n_factorial = str(math.factorial(n))  # n!
cnt = 0
#  팩토리얼 계산값의 1의 자리부터 처음 0이 아닌 숫자가 나오기까지 0의 개수 카운트
for i in range(len(n_factorial)-1, -1, -1):
    if n_factorial[i] == '0':
        cnt += 1
    else:
        break
print(cnt)