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

도움이 된 질문 글 

https://www.acmicpc.net/board/view/39870

글 읽기 - 1676 1%가 안 닿습니다 도움 부탁드립니다.

문제 

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

1676번: 팩토리얼 0의 개수

예제 입력 1 복사

10

예제 출력 1 복사

2

#include <iostream>
using namespace std;

int twoset[501];
int fiveset[501];
int tenset[501];

void makesumset(int n)
{
	int stnd = 2;
	while (stnd <= 500)
	{
		for (int i = stnd; i<= n; i+=stnd)
			twoset[i]++;
		stnd *= 2;
	}
	stnd = 5;
	while (stnd <= 500)
	{
		for (int i = stnd; i <= n; i += stnd)
			fiveset[i]++;
		stnd *= 5;
	}
	for (int i = 1; i <= n; i++)
		twoset[i] += twoset[i - 1];

	for (int i = 1; i <= n; i++)
		fiveset[i] += fiveset[i - 1];
	for (int i = 0; i <= n;i++)
		tenset[i] = (twoset[i] <= fiveset[i]) ? twoset[i] : fiveset[i];
}

int main(void)
{
	int n;
	cin >> n;
	// n 0 ~ 500
	makesumset(n + 1);
	cout << tenset[n]; 
}

5의 배수도 25, 125 등 제곱 처리해주었어야 하는데 안해서 한번 틀림

 

누적해서 비교하고 구하는 식으로 했다! 

 

stnd는 standard 즉 기준이고 2랑 5를 기준으로 다시 2를 곱하고 5를 곱하는 식으로 수를 점점 크게해서 그의 배수는 +1시켜준다. 

 

그리고 twoset 과 fiveset은 그 전 앞에 있는 수에 자신을 더한 값이 truly 곱해진 2의 개수, 5의 개수가 되고 

 

tenset에서는 그 둘이 10이 만들어질 때 즉 더 작은 수를 기준으로 세도록 했다. ? : 부분 

 

추가로  makesumset은 500까지 전부 구할 필요 없고 n까지만 구하면 충분하므로 makesumset에서 n (넉넉잡아 n + 1)을 받도록 했다. 

 

primeset문제에서 약간 아이디어 얻어서 풀었음!