BOJ 1676: 팩토리얼 0의 개수

#BOJ 1676: 팩토리얼 0의 개수

1676번: 팩토리얼 0의 개수

#풀이

팩토리얼 을 구하는 것인데 n의 범위가 500까지라서 long long 의 범위도 벗어나는 숫자이다.

 

맨 처음에는 직접 팩토리얼을 계산해서 나머지연산을 해서 구했는데 예상대로 오버플로우가 났다.

 

일단 팩토리얼은 5! = 5X4X3X2X1 이다. 이걸 다시 바꾸면 5! = 4! X 5 이다.

 

그냥 dp랑 엇비슷하게 풀 수 있다.

i! = (i-1)! X i 

이렇게 생각하고 풀 수 있다.

 

하지만 여기선 팩토리얼의 수를 구하는 것이 목적이 아니라 1의 자리 부터 0의 개수를 구하는 것이다.

 

0은 사실상 10 이기 때문에 소인수 분해를 해서 2X5의 개수를 찾으면 된다.

 

이걸 다시 점화식을 쓰면

R(i) 의 2x5의 개수

R(i!) = R((i-1)!) + R(i) 

 

이렇게 풀면 간단하게 풀 수 있다.

 

#코드

#include<iostream>

using namespace std;

int n;
int num[2] = { 2,5 };
int arr[2];
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n;
	for (int i = 1; i <= n; i++) {
		int temp = i;
		for (int j = 0; j < 2; j++) { // 2와 5의 개수 구하기
			if (temp % num[j] == 0) {
				temp = temp / num[j];
				arr[j]++;
				j--;
			}
		}
	}
	if (arr[0] < arr[1]) { // 2와 5의 짝을 이뤄야하므로
		cout << arr[0] << '\n';
	}
	else {
		cout << arr[1] << '\n';
	}
	
	return 0;
}