2004번 조합 0의 개수 with C++

문제

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

2004번: 조합 0의 개수

 

해결한방법

1. n! 에서 2의 개수를 two변수에 5의 개수를 five변수에 저장한다.
2. k!에서 2의 개수를 two변수에서 빼고 5의 개수를 five변수에서 뺀다.
3. (n - k)!에서 2의 개수를 two변수에서 빼고 5의 개수를 five 변수에서 뺀다.
4. two와 five중 더 작은 수를 출력한다. 

#include <iostream>
using namespace std;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	int n, m;
	cin >> n >> m;
	int diff = n - m;

	int five = 0, two = 0;
	int temp;

	temp = n;
	while (temp) {
		five += temp / 5;
		temp /= 5;
	}
	temp = n;
	while (temp) {
		two += temp / 2;
		temp /= 2;
	}

	temp = m;
	while (temp) {
		five -= temp / 5;
		temp /= 5;
	}
	temp = m;
	while (temp) {
		two -= temp / 2;
		temp /= 2;
	}

	temp = diff;
	while (temp) {
		five -= temp / 5;
		temp /= 5;
	}
	temp = diff;
	while (temp) {
		two -= temp / 2;
		temp /= 2;
	}

	if (two < five)
		cout << two;
	else
		cout << five;

	return 0;
}

 

개선한 방법

n!에서 5의 N승을 구할때 5, 25, 125, ... 으로 나눠서 나오는 몫을 다 더하는 방법으로 구하기 위해 5를 나눈 몫을 더하고 5로 5로 나눈 몫으로 다시 5로 나누고 를 반복했는데 나누는 수를 for문을 통해서 키워가면서 6개의 while문을 2개의 for문으로 줄일 수 있었습니다.

#include <iostream>
using namespace std;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	long n, m;
	cin >> n >> m;
	long diff = n - m;

	int two = 0, five = 0;
	for (long i = 2; i <= n; i *= 2)
		two += n / i - m / i - diff / i;
	for (long i = 5; i <= n; i *= 5)
		five += n / i - m / i - diff / i;

	if (two < five)
		cout << two;
	else
		cout << five;

	return 0;
}

 

개선한 방법의 코드는 백준 alex9801님의 코드를 참고했습니다.

https://www.acmicpc.net/source/2119632