백준 1676 파이썬 (팩토리얼 0의 개수)

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

처음에는 팩토리얼 구하면서 중간중간 그 값을 10으로 나누어 오버플로우 방지하고 카운트 올리고 뭐 이런방법으로 하는 거일줄 알았지만 생각보다 단순했다.

1. 팩토리얼로 얻을 수 있는 수를 인수 분해 했을때, 0이 늘어나는 순간은 10(2x5)이 곱해지는 순간이다.
2. 따라서 5의 개수를 찾는 문제이다. (2와 5를 찾는다는게 더 정확하지만 5만 찾아도 상관이 없다 -> 2랑 5가 짝인데 5가 더 적게 등장하므로)
   ex) 5! = 1 * 2 * 3 * 4 * 5 -> 5 1개
   10! = 1 * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 * 10 -> 5, 10 2개
3. 5의 배수 개수는 5로 나눈 몫으로 계산한다 (10//5 = 2)
4. 문제는 제곱수도 생각을 해줘야 한다. 25의 경우 5가 두번 들어가 있기 때문!
   

💻 Code

n = int(input())
cnt = 0

while(n>1):
    cnt += n // 5
    n = n // 5

print(cnt)

• // 연산자 (몫을구하고 나머지버림) 를 사용
• 25 와 125같은 제곱수를 생각해야 하므로 while문을 활용해 계속해서 나눠주었다.

📌 더 간단한 풀이

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

• 문제에서 n의 범위는 500까지 이므로 제곱수는 125까지만 생각하면 된다. -> while문 사용 대신에 print문을 활용

어떻게 접근해야할지 모르겠을 때는 수열로 나열한다음 규칙을 찾는 법도 나쁘지 않은 것 같다.