[백준/2004] 조합 0의 개수

1. 문제

 

 

 

 

2. 접근 방법

중고등학교때 열심히 배웠던 이항계수와 관련된 문제이다.

다음과 같이 n=5, c=2 의 경우를 가정해보자.

 

계산된 값은 10 이다. 그러므로 문제에서 요구하는

'뒤에서부터 처음으로 0이 아닌 값이 나올 때까지의 0의 개수' 는 1 이다.

이런 식으로, 문제가 요구하는 값을 찾아야 하는데 문제는 범위가 1 ~ 20억이라

자칫하면 시간 초과 오류가 발생할 수 있다.

일반적인 순차 접근은 어림도 없으니, 이제 효율적인 알고리즘을 알아보자.

 

문제에서 요구하는, 뒤에 0이 발생하는 경우는, 2와 5가 만나야만 가능하다.

2와 5를 곱하면 10이다. 어떤 수에 10이 곱해지면 뒤에 0이 하나 생기는 것이다.

그러므로, 우리는 다음의 알고리즘을 적용하면 답을 구할 수 있다.

 

---

(1) 분자를 소인수분해하여 2의 개수와 5의 개수를 찾는다.

(2) 분모를 소인수분해하여 2의 개수와 5의 개수를 찾는다.

(3) 분자의 2의 개수에서 분모의 2의 개수를 뺀다.

(4) 분자의 5의 개수에서 분모의 5의 개수를 뺀다.

(5) 남은 2의 개수와, 남은 5의 개수 중 작은 값을 출력한다.

---

위의 알고리즘까지 이해했다면 절반은 온 것이다.

이제 중요한 과정이 남았다.

소인수분해하여 2의 개수와 5의 개수를 찾는 알고리즘을 알아보자.

 

---

* 2의 개수를 구하는 알고리즘

(1) 2의 개수를 구할 대상을 N, 2의 개수를 M 이라고 가정한다.

(2) M에 N / 2의 값을 더한다.

(3) M에 N / 4의 값을 더한다.

(4) M에 N / 8의 값을 더한다.

...

(5) M에 N / (2의 배수 중 N보다 작은 숫자) 를 더한다.

(6) 위의 과정을 거치면, M은 N을 소인수분해했을 때 2의 개수이다.

 

* 5의 개수를 구하는 알고리즘

(1) 5의 개수를 구할 대상을 N, 5의 개수를 M 이라고 가정한다.

(2) M에 N / 5의 값을 더한다.

(3) M에 N / 25의 값을 더한다.

(4) M에 N / 125의 값을 더한다.

...

(5) M에 N / (5의 배수 중 N보다 작은 숫자) 를 더한다.

(6) 위의 과정을 거치면, M은 N을 소인수분해했을 때 5의 개수이다.

---

위의 알고리즘은 O(log N) 형태의 시간 복잡도를 가지므로,

범위가 1 ~ 20억이라고 해도 시간 안에 문제풀이가 가능하다.

 

 

 

3. 구현

#include <iostream>
#include <algorithm>

using namespace std;

typedef long long ll;

pair<ll, ll> PF(int n)
{
	pair<ll, ll> res;

	res.first = 0;
	res.second = 0;

	for (ll i = 2; i <= n; i *= 2)
	{
		res.first += (n / i);
	}

	for (ll i = 5; i <= n; i *= 5)
	{
		res.second += (n / i);
	}

	return res;
}

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

	int n, m;
	cin >> n >> m;

	pair<ll, ll> den1 = PF(n - m), den2 = PF(m), nom = PF(n);
	ll fives = nom.second - den1.second - den2.second;
	ll twos = nom.first - den1.first - den2.first;
	cout << min(fives, twos) << '\n';

	return 0;
}