백준 1676번 팩토리얼 0의 개수 // C++

문제

 

N!에서 뒤에서부터 처음 0이 아닌 숫자가 나올 때까지 0의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다. (0 ≤ N ≤ 500)

출력

첫째 줄에 구한 0의 개수를 출력한다.

 

---

 

풀이

 

제일 뒤에 0의 개수는, n!에서 2와 5의 개수 중 작은 값이다.

 

따라서, n까지의 수에서 2와 5가 나오는 횟수를 각각 세어서 그 중 더 작은 값을 출력하면 된다.

 

---

 

코드

#include <iostream>
#include <algorithm>

using namespace std;

int solve();

int N;
int two[501] = { 0, };
int five[501] = { 0, };

int main() {
	cin >> N;

	cout << solve();

	return 0;
}

int solve() {
	int twoCount = 0;
	int fiveCount = 0;

	for (int i = 1; i <= N; i++) {
		if (i % 2 == 0) {
			two[i] = two[i / 2] + 1;
			twoCount += two[i];
		}
		if (i % 5 == 0) {
			five[i] = five[i / 5] + 1;
			fiveCount += five[i];
		}
	}

	return min(twoCount, fiveCount);
}