[백준] 3474번 교수가 된 현우

https://www.acmicpc.net/problem/3474

3474번: 교수가 된 현우

이렇게 제출했는데 시간초과가 났다.

#include <iostream>
#include <vector>
using namespace std;

int main() {
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);
	int n;
	cin >> n;
	vector<int> v(n);
	for (int i = 0; i < n; i++) {
		cin >> v[i];
	}
	int five[] = { 1, 5, 25, 125, 625, 3125, 15625, 78125, 390625, 1953125, 9765625, 48828125, 244140625, 1220703125 };
	int index = 1;
	int vectorIndex = 0;
	int now = 0;
	int previous = 0;
	for (int i = 1; i <= 1000000000; i++) {
		int increase;
		for (int j = index; j >= 0; j--) {
			if (i % five[j] == 0) {
				increase = j;
				if (j == index)
					index++;
				break;
			}
		}
		now = previous+ increase;

		if (i == v[vectorIndex]) {
			cout << now << '\n';
			vectorIndex++;
			if (vectorIndex == n) break;
		}
		previous = now;
	}
	return 0;
}

대략 반복문 수행 횟수가 10000000 넘어가면 1초 넘는데 얘는 1000000000에 이중 for문이니까 당연히 시간초과가 난다.

 

이렇게 다시 풀었다.

#include <iostream>
#include <vector>
using namespace std;

int main() {
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);
	int n;
	cin >> n;
	for (int i = 0; i < n; i++) {
		int num;
		cin >> num;
		int count = 0;
		for (int j = 5; j <= num; j *= 5) {
			count += num / j;
		}
		cout << count << '\n';
	}
	return 0;
}