백준 1676 팩토리얼 0의 개수

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

문제와 채점은 위 사이트에서 확인 하실 수 있습니다

 

이 문제는 n팩토리얼을 하였을 때 끝자리부터 0이 아닌수가 나올때 까지의 0의 개수를 구하는 문제입니다. n이 500까지 가능하므로 팩토리얼을 구하는 것은 어마어마하게 큰수가 나오게 됩니다. 

 

따라서 어떻게 하면 0을 찾을 수 있을까를 생각해보면 기본적으로 끝자리에 0이 생기기 위해서는 2와 5라는 숫자가 필요하게 됩니다. 따라서 이 숫자들의 개수를 세어주면 되는데 기본적으로 n!의 진행에서는 5보다 2가 훨씬 많으므로 저희는 5의 개수만 셈으로써 0이 몇개나오는지 알 수 있습니다. 

이 때 주의할 점은 5의 제곱수가 나올 때 입니다. 25는 5가 2번 곱해진 것이므로 0을 두개 만들 수 있습니다. 또한 125는 0을 3개를 만들 수 있습니다.

따라서 주어진 n을 5로 나눈 몫과 25로 나눈몫과 125로 나눈 몫을(n이 500까지 가능하므로) 더하면 최종적으로 답을 구할 수 있습니다.

 

다음은 코드입니다.

 

#include <iostream>

using namespace std;

int main(void) {
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	int n;
	int zero = 0;
	cin >> n;
	zero = n/5 + n/25 + n/125;
	cout<<zero;
	return 0;
}