[백준2004] 조합 0의 개수 (C++)

BOJ 바로가기

시간초과 코드

#include <iostream>
using namespace std;

int func2(int);
int func5(int);

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	int n, m;
	cin >> n; cin >> m;
	int num = min(func2(n) - (func2(n - m) + func2(m)), func5(n) - (func5(n - m) + func5(m)));
	cout << num;
	return 0;
}

int func2(int x) {
	int count = 0;
	while (x>0) {
		int k = x;
		while (1) {
			if (k % 2 == 0) {
				count++;
				k /= 2;
			}
			else
				break;
		}
		x--;
	}
	return count;
}

int func5(int x) {;
	int count = 0;
	while (x > 0) {
		int k = x;
		while (1) {
			if (k % 5 == 0) {
				count++;
				k /= 5;
			}
			else
				break;
		}
		x--;
	}
	return count;
}

과도한 반복문 사용으로 시간초과가 뜨는 코드이다.
구글링의 힘을 빌려 코드를 다시 짜 보았다.

#include <iostream>
using namespace std;

long long func2(long long);
long long func5(long long);

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	long long n, m;
	cin >> n; cin >> m;
	long long num = min(func2(n) - (func2(n - m) + func2(m)), func5(n) - (func5(n - m) + func5(m)));
	cout << num;
	return 0;
}

long long func2(long long x) {
	long long count = 0;
	for(long long i = 2; i <= x; i *= 2)
		count += x / i;
	return count;
}

long long func5(long long x) {
	long long count = 0;
	for (long long i = 5; i <= x; i *= 5)
		count += x / i;
	return count;
}

int 자료형을 long long 자료형으로 바꿔주고 구현 방식을 달리했다.

100!에 5가 몇 개 들었는지 파악하기 위해 이전 방법처럼 1부터 100까지의 숫자를 5로 나눌 수 있는 횟수를 더해주는 방법을 사용할 수도 있지만 가장 간단한 방법은 100을 5, 5^2로 나는 몫을 더해주는 것이다.

100=5*20

100=25*4

따라서 20+4=24

상당히 간편한 방법이다. 기억해두는 편이 좋을 것 같다.