[백준] 1676 팩토리얼 0의 개수 - 수학, 정수론

[ 문제링크 ]

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

🚩 조건

N!를 구해나가는 과정에서 나오는 수의 0이 아닌 마지막 자리만 보면 된다고 생각했다.

만약 맨 마지막 자리가 0이 된다면, 그 자리는 항상 0일 것이고, 그럼 answer++ 후 고려할 마지막 자리를 앞으로 한 칸 옮기면 된다고 생각했다.

근데 이렇게 구현했더니 맞는 것 같은데 틀렸습니다가 나와서 반례를 찾아봤더니, 아래 케이스에서 결과가 달랐다.

입력 > 25

출력 > 5

정답 > 6

결론 먼저 말하자면, 맨 뒷자리만 관리하면 안 된다. 이렇게 생각한 사람들이 꽤 많나보다..ㅎ

올바른 접근 방법은 아래와 같다.

1. 0이 늘어나는 순간은, 10이 곱해지는 순간이다.

2. 따라서 소인수분해 시 5의 개수를 찾는 문제이다. (2와 5를 찾는다는 말이 더 정확하지만, 2와 5가 짝인데 5가 더 적게 등장하므로 5의 개수만 세는 것이 더 효율적이다)

3. 이를 구현하기 위해, N을 5로 나눈 몫(=5의 배수 개수)을 구한다. 그리고 제곱수를 생각해줘야 하므로, while문을 통해 반복한다.

N=int(input())
answer=0

while N>1:
    answer+=N//5
    N=N//5

print(answer)

효율은 떨어지지만 개쩌는 풀이를 발견했다.. 역시 파이썬....

math.factorial을 통해 n 팩토리얼을 계산한 뒤, str로 바꾸고 뒤집어준다.

그 후 0이 끝날 때까지 개수를 세준다..

시간초과가 안 뜨는게 신기하다

from math import factorial
n = int(input())
cnt = 0

for x in str(factorial(n))[::-1]:
	if x != '0':
    	break
    cnt += 1
    
print(cnt)