백준 #2004

★★★★★★★☆☆☆

문제 접근 방식

처음에는 팩토리얼로 조합의 개수를 직접 구해 해결하려고 했었다. 조합의 공식이 n!/r!(n-r)! 이므로, n의 최댓값이 너무 크게 주어져 integer overflow가 발생한다. 시간적으로도 불가능하고, 그래서 고민을 오래동안 했는데, 결국 0의 개수라는 게 10이 몇 번 곱해졌냐라는 뜻인데, 곱해서 10이 나오는 수는 2,5이다. 그래서 만약 10! 이면 1*2*3..*10 이런 식에서 각수에 2와 5가 있는지를 찾으면 해결할 수 있을 줄 알았다 하지만, 20억 팩토리얼이면 for문을 20억 번 돌아야 하므로 주어진 시간 내에 절대 해결할 수가 없었다. 그러다가 종이에 팩토리얼을 막 쓰고 (아마 25팩이었던 것 같다) 멍 때리고 있었는데 5의 배수는 결국 5를 포함한다. 그리고 만약 1~25까지의 수가 있으면 5의 개수가 5개이고 이는 25/5라는 걸 알았다. 즉, n/5가 5의 배수의 개수라는 걸 알았고, 25나 125 같은 수는 5의 배수이지만 소인수 분해했을 때 5의 지수가 1 이상이다. 즉 , n/5의 개수+n/25의 개수+ n/5^x의 개수를 더하면 5의 개수를 알 수 있고 2 또한 마찬가지라는 걸 알았다. 그래서 분자의 5의 개수와 2의 개수 중 작은 것 - 분모의 5의 개수와 2의 개수 중 작은 것을 구하면 0의 개수를 구할 수 있었다.

int findfive(int n) {
	_5count = 0;
	for (int i = 1; i <= 13; i++) {//5의 13제곱이 20억까지의 마지노선임
		_5count += n / pow(5, i);
	}
	return _5count;
}
int findtwo(int n) {
	_2count = 0;
	for (int i = 1; i <= 30; i++) {
		_2count += n / pow(2, i);
	}
	return _2count;
}

이 함수들은 각각 5의 개수와 2의개수를 찾는 함수들이다. 20억까지의 5의 최대 거듭제곱과 2의 최대 거듭제곱의 지수를 미리 설정해놓았다.

 

---

    	den_2count = findtwo(n); //분자의 2개수
	den_5count = findfive(n); //분자의 5개수

	if (den_2count == 0 || den_5count == 0) { cout << 0; return 0; }

	num_2count = findtwo(m) + findtwo(n - m); //분모의 2개수
	num_5count = findfive(m) + findfive(n - m);//분자의 5개수

	_2count = den_2count - num_2count;  //총 2의 개수
	_5count = den_5count - num_5count; //총 5의개수
	count_ = (_2count < _5count) ? _2count : _5count; //더작은것을 고름

	cout << count_;

시간 복잡도: O(1) findfive, findtwo함수가 가장 많은 연산을 하는데 각각 13번, 30번이 최대이기 때문이다.

느낀 점: 생각을 많이 해야 하는 문제고 이 문제를 풀었다는 게 신기하다.