백준 1676번: 팩토리얼 0의 개수

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

1676번: 팩토리얼 0의 개수

 

 

0. 알고리즘 분류

 수학

 

 

1. 문제

 

 

2. 풀이

처음엔 문제를 이해하지 못했지만, 그냥 단순히 N!의 약수 중 10의 개수를 세는 문제이다. 10 = 2 * 5이고, 2는 모든 짝수에 들어있으므로 상대적으로 적은 5의 개수만 세면, 10의 개수를 알 수 있다.

 

 여기서 주의해야할 점이, 25 = 5 * 5이므로 5가 2개이다. 필자도 처음에 이걸 모르고 단순히 n/5로만 계산했다..

 

 

3. 코드

#include <iostream>

using namespace std;

int main(void) {
	int n;
	cin >> n;
	
	int ans = 0;
	for (int i = 5; i <= n; i *= 5) {
		ans += n/i;
	}
	
	cout << ans;
	
	return 0;
}