N!의 표현법


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

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

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

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

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

▣ 입력예제 1 
12

▣ 출력예제 1
2


풀이

0의 개수는 소인수 분해 했을 경우 2 * 5의 개수에 의해 결정된다.
그래서 N!의 값을 구하고 0의 개수를 세는게 아니라 2 * 5의 개수만 구하면 된다.

void solve()
{
	int n;
	cin >> n;

	// 0의 개수는 2 * 5로 만들어짐

	int count2 = 0, count5 = 0;
	for (int i = 2; i <= n; ++i)
	{
		int temp = i;
		int j = 2;
		while (true)
		{
			if (temp == 1)
				break;

			if (temp % j == 0)
			{
				if (j == 2)
					count2++;
				if (j == 5)
					count5++;

				temp /= j;
			}
			else
			{
				j++;
			}
		}
	}

	if (count2 < count5)
		cout << count2;
	else
		cout << count5;
}

전체 코드

#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>
#include <string.h>
#include <ctype.h>
#include<iostream>
#include <fstream>
#include <vector>

using namespace std;

void solve()
{
	int n;
	cin >> n;

	// 0의 개수는 2 * 5로 만들어짐

	int count2 = 0, count5 = 0;
	for (int i = 2; i <= n; ++i)
	{
		int temp = i;
		int j = 2;
		while (true)
		{
			if (temp == 1)
				break;

			if (temp % j == 0)
			{
				if (j == 2)
					count2++;
				if (j == 5)
					count5++;

				temp /= j;
			}
			else
			{
				j++;
			}
		}
	}

	if (count2 < count5)
		cout << count2;
	else
		cout << count5;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	//freopen("input.txt", "rt", stdin);

	solve();

	return 0;
}

참고