백준 11687(팩토리얼 0의 개수)

www.acmicpc.net/problem/11687

11687번: 팩토리얼 0의 개수

 

0이 어떻게 만들어지는지에 대한 문제이다.

 

어떤 n!을 파보던 2의 거듭제곱 갯수가 5의 거듭제곱 갯수보다 항상 많으므로 

n!에서 0은 5의 거듭제곱 갯수가 결정한다. 

 

5의 거듭제곱 갯수의 합을 구하면 되는 문제이다.

#include<iostream>
using namespace std;
#define MAX 100000000

int sum;

int main() {
	int M;
	cin >> M;
	for (int i = 1; i <= MAX; i++) {
		int tmp = i;
		int num = 1;
		while (tmp % 5 == 0) {
			num++;
			tmp /= 5;
		}
		sum += num;
		if (sum == M) {
			cout << 5 * i << '\n';
			return 0;
		}
		else if (sum > M) {
			cout << -1 << '\n';
			return 0;
		}
	}
}

 

다른 사람 풀이를 보니깐 이분탐색으로 더 빨리 찾을 수 있는 것 같다.