[c++]백준-3474 교수가 된 현우

1. 문제

문제는 다음과 같다 나는 처음에 그저 brute force한 방법으로 값을 구한 뒤 substr함수를 이용해서 0을 잘라내려 했으나 굉장히 무모한 도전이었다. 왜냐하면 100!의 값만 하더라도 컴퓨터가 출력해낼 수 있는 값인 long long자료형의 범위마저 훌쩍 뛰어 넘어버리기 때문이다. 따라서 좀 더 고민을 하던 중 뒤가 0이 나오는 경우를 생각해보았다. 이 때 0이 나오는 경우는 2와 5가 결합된 경우 밖에 없다는 사실을 알게 되었다. 따라서 두 번째 생각한 방법이 만약 5를 입력받았으면 

5 4 3 2 1의 수를 모두 소인수 분해한 다음 2와 5의 개수를 세서 더 작은 값을 출력하는 방법이었다. 이러한 방법으로 작성한 나의 코드는 다음과 같다. 

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int t; // 테스트 개수
int n;
int two;
int five;
int temp;
vector<int> v;
void sol(int num) {
	while (num > 1) {
		temp = num;
		while (num > 1) {
			if (num % 2 == 0) {
				two++;
				num /= 2;
			}
			else break;
		}
		num = temp;
		while (num > 1) {
			if (num % 5 == 0) {
				five++;
				num /= 5;
			}
			else break;
		}
		num = temp - 1;
	}
}


int main() {
	cin >> t;

	for (int i = 0; i < t; i++) {
		cin >> n;
		sol(n);
		if (two >= five) v.push_back(five);
		else v.push_back(two);
		two = 0; five = 0;
		
	}

	for (int j = 0; j < t; j++) {
		cout << v[j] << endl;
	}


	return 0;
}

위의 코드대로 결과를 출력하면 

정답 출력처럼 결과가 나오기는 한다. 

정답출력은 아래와 같다. 

나의 결과는 다음과 같다. 

정답을 출력해서 기쁜 마음에 채점을 하러갔으나 돌아오는 결과는 다음과 같았다. 

시간초과라니... 그래서 더욱 시간을 줄일 수 있는 방법을 생각해보았다. 처음에는 vector를 사용한 것이 시간에 영향을 주었을까봐 배열로 바꾼 후 실행해봤지만 T의 size 범위가 정해지지 않아서 이는 올바르지 못한 방법이었다. 조금 더 생각을 해보니 5로 계속 나누는 연산을 수행하는 것보다 5로 나누고 25로 나누고 125로 나누고하는 방법 즉 2와 5를 제곱시켜 나누는 방법이 더 연산의 횟수를 적게 할 것이라는 생각이 들었다. 

왜냐하면 어떤 수를 나눈다는 2로 나눈다는 것은 이 안에 2가 몇 개 들어있는지 파악하는 일이기 때문이다. 

따라서 작성한 코드는 다음과 같다. 

#include <iostream>
#include <algorithm>
//#include <vector>
using namespace std;
int T; // 개수
int n;
int two = 0;
int five = 0;
//vector<long long> v;
int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	cin >> T;
	for (int i = 0; i < T; i++) {
		cin >> n;
		two = 0; five = 0;
		for (int j = 2; j <= n; j *= 2) {
			two += n / j;
		}
		for (int u = 5; u <= n; u *= 5) {
			five += n / u;
		}

		cout << min(two, five) << endl;
		
	}
	
	return 0;
}