백준 3473번 - 교수가 된 현우

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

3474번: 교수가 된 현우

풀이 과정

 N!에서 뒤에 오는 0의 개수를 구하는 문제이다. 어떤 수 뒤에 0이 온다는 것은, 10이 곱해져 있다는 뜻이고, 10이 곱해져있다는 뜻은 2와 5가 곱해져잇다는 말이다. 어떤 수가 있을 때 소인수 2의 개수가 소인수 5의 개수보다 많으므로, N!에서 5가 몇번 곱해졌는지 구하면 된다. 입력된 수를 5로 나누면 해당 수까지 5의 배수가 몇 개인지 알 수 있다. 하지만 (25!에서 곱해진 요소들) 1 *... * 5 * ... * 10 * 11 * ... * 15 * 16 * ... 25 이런 식으로 5의 배수를 구하다보면 25와 같은 수는 5가 2번 곱해져있는데 이런 수들을 찾아내기 위해서 5의 n승이 몇번 포함되어 있는지도 확인해주어야 한다. 25가 5로 나눌 때 한번 포함되었고, 25로 나눌 때 또 한번 5를 찾아내게 된다.

 

느낀 점

 정수, 수학 파트가 약하다고 느꼈다. 2와 5의 요소가 포함되어야하고, 5의 개수를 구하는 것까지는 떠올렸지만 소인수 5의 개수를 구하는 방법을 떠올리지 못했다. 팩토리얼에 대한 이해가 부족했던 것 같고 감을 키울 수 있는 좋은 문제였다.

 

#include<bits/stdc++.h>
using namespace std;

int n, num, ret;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	cin >> n;
	for (int i = 0; i < n; i++) {
		ret = 0;
		cin >> num;
		for (int j = 5; j <= num; j *= 5) {
			ret += num / j;
		}
		cout << ret << "\n";
	}
	return 0;
}