[Algorithm] 28. N!에서 0의 개수

인트로

본 문제는 수학적인 사고를 요구합니다.

본 문제를 해결하기 어렵다면 이전 포스팅 N!의 표현법을 풀어보시길 권장합니다.

[Algorithm] level1 : N!의 표현법

 

N!에서 0의 개수

문제

자연수 N이 입력되면 N! 값에서 일의 자리부터 연속적으로 ‘0’이 몇 개 있는지 구하는 프로그램을 작성하세요.
[예시]
5! = 5 X 4 X 3 X 2 X 1 = 120으로 일의 자리부터 연속된 ‘0’의 개수는 1입니다.
12! = 479001600으로 일의 자리부터 연속된 ‘0’의 개수는 2입니다.

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

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

입력

12

출력

2

코드 설명

N!의 표현법 문제와 해결방법이 유사하다.

 

가령 어떤 숫자가 0으로 끝난다면 A라는 값에 10이 곱해진 형태이다.

나아가 00으로 끝난다면 100이 곱해진 형태이다.

 

[한 단계 더 생각해보기]

10을 소인수 분해하면 2 X 5로 표현된다.

즉 어떤 수를 소인수 분해했을 때 2와 5가 하나씩 존재한다면 해당 수는 0으로 끝난다는 의미다.

 

경우의 수를 나열해 규칙을 찾아보면 2와 5가 쌍으로 존재해야 끝자리에 0이 하나씩 붙어간다. 

2 X 5 = 10

2 X 2 X 5 X 5 = 100

2 X 2 X 2 X 5 X 5 = 200  

2 X 2 X 2 X 5 X 5 X 5 X 5 X 5= 25000

 

문제를 코드로 구현해보자.

#include <iostream>
#include <vector>

using namespace std;

int main()
{
	int n, res;

	cin >> n;

	vector<int> vec(n + 1, 0);

	for (int i = 2; i <= n; i++)
	{
		int temp = i;
		int div = 2;

		while (true)
		{
			if (temp % div == 0)
			{
				vec[div]++;
				temp /= div;

				if (temp == 1)
					break;
			}
			else
				div++;
		}
	}

	res = vec[2] <= vec[5] ? vec[2] : vec[5];

	cout << res;
}