[백준 3474번 / C++] 교수가 된 현우

해당 문제는 어떻게 접근해야할지 먼저 생각을 하고 들어가자. 

 

3! 이면 끝자리의 0의 개수가 몇개인가?  0개이다. 

5! 이면 끝자리의 0의 개수가 몇개인가?  1개이다.

10! 이면 끝자리의 0의 개수가 몇개인가? 2개이다. 

18! 이면 끝자리의 0의 개수가 몇개인가? 3개이다.  

 

뭔가 규칙이 보인다. 

숫자에 0이라는 수를 끝에 위치하게끔 만들수 있는 수는 10이다. 

10을 만들기 위해서는 2와 5가 필요하다. 

그렇기 때문에 n!에서 2와 5의 쌍을 가지고 있는 개수를 세주면 된다. 

 

2의 경우에는 짝수이면 모두 포함되기 때문에 굳이 카운트 해 줄 필요가 없다.(워낙 많기 때문) 

그렇기 때문에 5라는 숫자가 총 몇개 들어가있는지만 카운트 해주면 된다. 

 

만약, 18! 에서 5의 개수는 18/5 를 해주면 몫이 3이기 때문에 5의 총 개수는 3개라는 것을 알 수 있다. 

 

여기서 주의 해야할 점은 25, 625 ... 같은 5의 제곱에 해당하는 값들은 5가 2번, 3번씩 들어가기 때문에 

이 점을 주의해서 해당 값들도 카운트 해줘야한다. 

 

#include <iostream>
using namespace std; 
int main() {
	ios::sync_with_stdio(0); 
	cin.tie(0); cout.tie(0); 
	int n; cin >> n; 
	for (int i = 0; i < n; i++) {
		int a; cin >> a; 
		int mul5 = 5;
		int sum = 0; 
		while (mul5 <= a) {
			sum += a / mul5; 
			mul5 *= 5; 
		}
		cout << sum << "\n"; 
	}
}

 

3474번: 교수가 된 현우