[Baekjoon] 1676. 팩토리얼 0의 개수

1676. 팩토리얼 0의 개수
N!에서 뒤에서부터 처음 0이 아닌 숫자가 나올 때까지 0의 개수를 구하는 프로그램을 작성하시오.

🔍 나의 코드

n!을 계산한 후 직접 뒤에서부터 0의 개수를 센다.

import math

n = int(input())
n = math.factorial(n)
n = list(map(int, str(n))) #n을 리스트로 변환

ans = 0

for i in n[::-1]: #뒤에서부터 탐색
    if i == 0 : ans += 1
    else: break

print(ans)

🌀 정수를 리스트로 변환

: list(map(int,str(num)))

num = 232443
line = list(map(int,str(num)))
print(line) # 	[2, 3, 2, 4, 4, 3] 요소가 정수임.

x = 12345
list = list(str(x))
print(list) #['1', '2', '3', '4', '5'] 요소가 문자열임.

🌀 for문 : 리스트의 뒤에서부터 탐색, 리스트 뒤집기

list = [1,2,3,4,5]
for i in list[::-1]:
    print(i) # 5 4 3 2 1

• reversed_list = list[::-1]
• list.reverse() : 원본 리스트가 바뀜.
• reversed_list = list(reversed(origin_list))
  : 원본바뀌지 않음. 그냥 reversed()만 하면 타입이 list_reverseiterator이므로 list로 바꿔줘야 함.

🌀 팩토리얼 : math.factorial()

import math

print(math.factorial(3)) #6

---

🔍 다른 풀이

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

• 이전 나의 코드는 효율적인 방법이 아님. 수학적 지식이 필요!

참고한 풀이 링크

• 구하는 답 == x10의 개수
  ex) n = 36 일때, n! = 36 x 35 x ... x 3 x 2 x 1
  여기에서 x10의 개수를 구하면 됨. (10 = 2 x 5)
  ➡️ 소인수분해 했을 때 2와 5의 지수 중 더 작은값이 0의 개수(구하는 답)이다.
• x2는 짝수를 새로 곱해줄 때마다 증가하고, x5는 5의 배수를 새로 곱해줄 때마다 증가하므로
  항상 2의 지수가 5의 지수보다 클 수 밖에 없다.
  ➡️ 5의 지수값이 곧 0의 개수(구하는 답)이다.
• N을 소인수분해하기는 어려우므로 우선, 1부터 N까지의 곱(n!)을 펼쳐놓고 생각해보자. n=36이라 할때, 36 x 35 x ... x 3 x 2 x 1 (1~36)중에
  5의 배수의 개수는? : 36//5 = 7개 (5, 10, 15, 20, 25, 30, 35)
• 하지만!!! 25=5x5처럼 하나의 수에 5가 여러번 들어있는 경우가 있다.
  이런 경우는 따로 더 카운팅을 해주어야 한다.
  ➡️ 0의 개수(구하는 답) = n//5 + n//25 + n//125
  n의 범위는 0<= n <= 500이므로 5, 25, 125까지만 나눈다.
  (n의 4제곱은 범위를 벗어난 625이므로 이에 대해서는 따로 나누어 카운팅 할 필요가 없다.)