[백준알고리즘] 1676번: 팩토리얼 0의 개수 -Python

[백준알고리즘] 1676번: 팩토리얼 0의 개수 -Python

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

1676번: 팩토리얼 0의 개수

 

오 되게 신기했던 문제다.

근데 생각보다 쉬웠다.

 

일단 팩토리얼을 진행한 후 0이 1의 자리부터 몇 개까지 있는가에 대한 문제이다.

테스트 케이스로 나와있는 10!의 경우 3628800이 나온다.

 

하지만 무작정 N!를 진행한 후에 0의 개수를 카운팅 하는 문제는 아닐 것이다.

일단 주어진 범위에서도 500!를 하더라도 엄청나게 큰 수가 나온다...

이거는 각자 계산을 해보도록 하자 :) 여기서

 

 

그러면 규칙이 있을텐데 그 규칙만 찾으면 된다!라고 생각하는 순간 5와 10에서만 0이 늘어날 것이라는 것을 눈치챘을 것이다. 10도 5의 배수이니 5로 나눴을 때 몫만큼 0이 존재하는 것 아닐까? 하고 그대로 제출해봤는데 틀렸다.

 

import sys

N = int(sys.stdin.readline())

print(N//5)

 

 

엥? 왜 안되지..?

 

그래서 아까 위에 올려둔 링크에서 계속 5씩 늘려가면서 확인해봤더니 25에서는 5개가 아닌 6개가 존재했다.

그렇다는건 25가 5를 두 번 곱한 값이니까 5의 제곱의 배수에서는 2씩 늘어나고 5의 세제곱의 배수에서는 3씩 늘어날 것이라는 것을 예상했다.

 

그럼 25로 나눈 몫도 추가로 더해주고 125로 나눈 몫도 추가로 더해주면 되겠네?

된다!

 

import sys

N = int(sys.stdin.readline())

print(N//5 + N//25 + N//125)

 

코드가 짧아서 설마했는데 다들 람다 쓰고 뭐 쓰고 하면서 짧았다 ㅎㅎ;

 

 

 

잘못된 점이나 부족한 점 지적해주시면 감사하겠습니다