[C/C++/Python] 백준 - 2004번 : 조합 0의 개수

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

2004번: 조합 0의 개수

수학 문제 너무 어려웡

조합을 통해 도출해낸 값의 끝자리 0의 개수를 출력하는 문제이다.

그리고 0의 개수는 어떻게 구할까

위 문제 예제처럼 끝자리 0의 개수가 2개라면 그 식은 x * 10^2라고 표현할 수 있다.

위 식을 소인수분해하면 2와 5의 개수가 각각 2개씩 있다는 것을 알 수 있다.

 

이렇듯 어떤 문제에서 끝자리 0의 개수를 구하라는 것은 소인수분해 했을 때 2와 5의 공통개수를 구하라는 문제와 같다.

이 문제 또한 2와 5의 개수를 구하면 되는데 일반적인 완전탐색 기법으로 구현하게 되면 시간초과가 발생한다.

그래서 빠른 방법이 필요한데, 이 부분은 다른 블로그를 참고 했다.

https://game-happy-world.tistory.com/26

백준 2004 - 조합 0의 개수(상세풀이)

위 방법으로 시간초과를 해결했다.

< C++ >

#include <iostream>
#include <list>
#include <queue>
#include <stack>
#include <string>
#include <cstring>
#include <vector>
#include <map>
#include <algorithm>
#include <cmath>
#include <bitset>
#define INF 987654321
#define Mod 9901
#define CUNLINK ios::sync_with_stdio(false),cin.tie(0), cout.tie(0)
#define ll long long
#define ENDL cout << endl
#define endl '\n'

using namespace std;

pair<ll, ll> cal(ll x) {
	ll Two = 0, Five = 0;
	for (ll i = 2; i <= x; i *= 2)
		Two += x / i;
	for (ll i = 5; i <= x; i *= 5)
		Five += x / i;
	return { Two, Five };
}

int main() {
	CUNLINK;
	ll a, b;
	cin >> a >> b;
	pair<ll, ll> lhs = cal(a);
	pair<ll, ll> rhs = cal(b);
	pair<ll, ll> chs = cal(a - b);
	cout << min(lhs.first - rhs.first - chs.first, lhs.second - rhs.second - chs.second);
	
	return 0;
}

< Python >

n,m = map(int, input().split())

def two_count(n):
    cnt = 0
    while n != 0:
        n = n//2
        cnt += n
    return cnt

def five_count(n):
    cnt = 0
    while n != 0:
        n = n//5
        cnt += n
    return cnt

print(min(two_count(n) - two_count(m) - two_count(n-m), five_count(n) - five_count(m) - five_count(n-m)))