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

[초기 접근 방법]

1. N! 을 구하자

2. 0의 개수를 세자

 

 

 

[생각]

위와 같이 심플한 방법으로 접근하면 문제에서 N의 범위가 500까지이기 때문에 'OverflowError'가 발생한다.

따라서 OverFlow를 방지하기 위해 N!을 하는 과정에서 수의 크기를 관리해주어야 한다.

 

이 때, N!의 1의 자리만 보존해도 되기 때문에

다음과 같이 코드를 작성한다.

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

        fact /= 10
        zeroCount += 1

 

 

 

[코드]

# 풀이 시간 : 10 + 25분
# 시간복잡도 : O(N)
# 공간복잡도 : O(1)
# 참고 : -

# 왜 이리 시간이 많이 걸렸지?

# 1 2 6 24 120 720(6!) 5040(7!)
# 0이 아닌 숫자가 나올 때까지의 수에서 팩토리얼을 계속 계산하자

# 첫번째 제출 코드
    # 1의 자리만 남는 코드가 아니다.
    # 결국 fact가 INF 값이 되고 만다.

    # 1의 자리만 남게 하면 된다.
    
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)