[백준] 1676번 : 팩토리얼 0의 개수 (Python)

문제 : https://www.acmicpc.net/problem/1676

 

N!에서 뒤에서부터 처음 0이 아닌 숫자가 나올 때까지 

0의 개수를 구하는 문제.

 

1. N!을 구해 0의 개수 세기

import sys

input = sys.stdin.readline

N = int(input()) # N

factorial = 1
answer = 0
    
for i in range(2, N+1):
    factorial *= i # 팩토리얼 구하기
    
factorial = str(factorial)[::-1] # 문자열 역순으로 배치
    
for i in factorial:
    if(i == '0'): # 0이면
        answer += 1
    else: # 아닐 시 반복문 종료
        break;

print(answer)

 

정통적인 방식으로 N!를 구해 0의 개수를 센다.

팩토리얼을 구하고, 문자열을 역순으로 배치 해 0의 개수를 count!

 

 

 

2. 5의 개수를 세서 0의 개수 구하기

import sys

input = sys.stdin.readline
N = int(input()) # N
    
# n!의 5의 개수 세기
def five_count(n):
    answer = 0
    while n != 0: # n이 0이 아닐 시
        n = n // 5 
        answer += n # 5로 나눈값을 더한다
    return answer
 
print(five_count(N))

 

10은 2와 5를 곱한 값이다.

즉, 0의 개수를 구한다는 건 다른 건 다 의미없고 2와 5의 개수만 구하면 된다.

 

그런데 언제나 2의 개수는 5의 개수보다 많으므로, 5의 개수를 count하면 된다!

단순히 5로 나누어 떨어지는 수는 25같이 5가 2번 있는 수를 고려할 수 없으므로, 정확히 5의 개수가 몇개인지 세면 그게 바로 0의 개수다.