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

풀이

팩토리얼을 실제로 계산해 뒤에서부터 0의 갯수를 세면 메모리 초과, 혹은 시간초과가 나온다. (파이썬은 문자열로 바로 바꿔서 계산하니 오류 없이 통과 된 코드도 있는 것을 확인하기는했지만.. ) 

이 문제는 팩토리얼 수를 구하는 목적으로 낸 문제가 아니기 때문에 본래의 목적대로 푸는게 좋겠다. 수를 곱했을 때 0이 붙는 상황을 생각해보면, 2X5가 곱해질 때 밖에 없다. 따라서 팩토리얼 수에 2와 5가 얼마나 곱해져있는지만을 생각하면 되는데, 2의 배수는 항상 5의배수보다 그 수가 많아질 수가 없다. 따라서 5의 배수의 갯수만을 생각하면된다.

이 때 주의할 점은 25와 125의 경우 한 번 곱해질 때 0이 각각 2개, 3개씩 붙는다는 점이다.

( 2^2 * 5^2 = 100(2개) / 2^3 * 5^3 = 1000(3개) )

코드는 매우 간단한데 비해 이해하는데 너무 오래걸렸다. 분발하자.

코드

처음 제출한 코드

n = int(input()) ans = 0 for i in range(5,n+1,5):     if i%25==0:         ans+=1     if i%125==0:         ans+=1     ans+=1 print(int(ans))

cs

두번째로 제출한 코드

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

cs