[C++] N!에서 0의 개수 🔥

📄문제

자연수 N이 입력되면 N! 값에서 일의 자리부터 연속적으로 ‘0’이 몇 개 있는지 구하는 프로그램을 작성하세요.

만약 5! = 5 × 4 × 3 × 2 × 1 = 120으로 일의자리부터 연속적된 ‘0’의 개수는 1입니다.
만약 12! = 479001600으로 일의자리부터 연속적된 ‘0’의 개수는 2입니다.

 

⬇️ 입력

첫 줄에 자연수 N(10<=N<=1,000)이 입력된다.

12

 

⬆️ 출력

일의 자리부터 연속된 0의 개수를 출력합니다.

2

 

📝 풀이

• 이 문제를 접근하는 방법은 다음과 같습니다.

팩토리얼의 각 값을 모두 소인수분해를 하여 2와 5의 조합이 있을경우, 이 값은 10을 곱하는것으로 간주됩니다.

10을 곱한다는것은 10진수에서 0을 추가하고 자리수를 올린다는 의미로, 0이 생기게 됩니다.

 

#include <iostream>

using namespace std;

static bool primeArr[1001];
static int primes[1001];

int isPrime(int x);
void divide(int x);

int main()
{
	for (int i = 0; i < 1001; ++i)
		primes[i] = primeArr[i] = 0;

	int N;
	scanf_s("%d", &N);

	for (int i = 2; i <= N; ++i)
		divide(i);

	printf("%d ", primes[5]);
}

void divide(int x)
{
	int primeIdx = isPrime(x);

	if (primeIdx == -1) // 소수가 맞음
	{
		++primes[x];
	}
	else if (x >= 2) // 소수가 아닌경우, 나누기
	{
		divide(x / primeIdx);
		divide(primeIdx);
	}
}

int isPrime(int x)
{
	// 이미 소수로 등록되어있다면, 즉시 리턴
	if (primeArr[x])
		return -1;

	// 해당 값으로 나눌것이 있어 소수가 아님
	for (int i = 2; i <= sqrt(x); ++i)
		if (x % i == 0)
			return i;

	// 소수를 검출하지 못한경우, x는 소수가 맞음
	primeArr[x] = true;
	return -1;
}

• 팩토리얼의 모든 곱셈을 소인수분해하여 각 소수의 개수를 저장합니다.
• 이 값에서 2와 5의 곱셈의 개수를 출력하면 됩니다.