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

 

 

<코드>

#include<iostream>
using namespace std;

int length, cnt = 0;
long long DP[501][2];

unsigned long long factorial(int x)
{
	if (x == 0) return 1;
	else return x * factorial(x - 1);
}

int main()
{
	
	cin >> length;

	DP[0][0] = 1;
	DP[0][1] = 0;

	for (int i = 1; i <= length; i++)
	{
		DP[i][0] = DP[i - 1][0] * i;

		while (DP[i][0] % 10 == 0)
		{
			DP[i][0] /= 10;
			cnt++;
		}
		DP[i][0] %= 1000;
		DP[i][1] = cnt;

	}

	cout << cnt;

}

 

long long형임에도 불구하고 20! 이후에는 숫자가 무진장 커져서 문제 조건에서 N이 0부터 500까지임을 보고 DP로 풀어야겠다고 생각하였다. 

20!만 넘어가도 숫자가 엄청 커진다.

 

 

풀이법은 간단하게 각 DP에서 맨 뒤의 0을 없애주고 count 해서 0의 개수를 세었고 남은 부분에서 1000을 또 나눠줘서 숫자가 자료형의 범위를 넘지 않도록 하였다.

 

 

<숏코드>

#include<iostream>
using namespace std;

int N;
int cnt2 = 0, cnt5 = 0;

int main()
{	
	cin >> N;

	for (int i = 2; i <= N; i *= 2) cnt2 += N / i;
	for (int i = 5; i <= N; i *= 5) cnt5 += N / i;

	cout << ((cnt2 < cnt5) ? cnt2 : cnt5);
}

 

DP풀이법 이외에 다른사람들의 코드를 찾아봤는데 맨 뒤의 0의 자리를 찾으려면 10의 약수인 2와 5의 개수를 센 후 그중에서 더 작은 개수만큼 2x5의 쌍이 만들어지므로 위와같은 풀이가 가능하다.

 

 

 

www.acmicpc.net/problem/1676

1676번: 팩토리얼 0의 개수