[백준] 1676번 팩토리얼 0의 개수 _ Python

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

1676번: 팩토리얼 0의 개수

 

 

---

 

1. Preview

시간 복잡도: O(N)

 

공간 복잡도: O(1)

 

유형: 수학

 

 

---

 

2. 초기 접근 방법

N! 값을 계산하고 결과값(처음으로 0이 아닌 숫자가 나올 때까지 0의 개수)을 구하기에는 N!의 값이 너무 커진다.

N! 의 값을 구할 때 1의 자리만 남겨줘도 0의 개수를 구할 수 있기 때문에,

  N! 계산 도중. 10으로 나눠질 경우 바로 나눠주어 zeroCount를 진행해준다.

 

 

---

 

3. 생각

-

 

 

---

 

4. 코드

N = int(input())

fact = 1
zeroCount = 0
for i in range(1, N + 1):
    fact *= i

    # 10으로 나눠질 경우
    if fact % 10 == 0:
        while True:  # 1의 자리만 남기도록 한다.
            if fact % 10 != 0:
                fact %= 10
                break

            fact /= 10
            zeroCount += 1

print(zeroCount)