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

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

2004번: 조합 0의 개수

---

 문제 풀이

'BOJ 1676번 : 팩토리얼의 0의 개수'와 비슷한 문제이다.

조합이기 때문에 (N! / (N-M)! M!) 의 2의 개수, 5의 개수 중 최솟값이 정답이다.

이전 'BOJ 1676번 : 팩토리얼의 0의 개수'에선 압도적으로 2의 개수가 많을 수밖에 없기에 5의 개수만 따졌지만

조합에서는 다르기 때문에 어느 것이 작은지 따져줘야한다.

브루트 포스로 해결하려면 시간이 절대적으로 모자라기 때문에 아이디어가 필요하다.

N을 K^i로 지속적으로 나누면 N!에 포함된 K의 지수의 개수를 구할 수 있다.

N을 K^i로 나누었을 때 나오는 값은 N보다 작거나 같은 K^i의 배수의 개수와 같기 때문이다.

예를 들어, N = 10 이고 K = 2 일 때

 10 / 2 = 5 (2, 4, 6, 8, 10)

 10 / 4 = 2 (4, 8)

 10 / 8 = 1 (8)

10! 에서 2의 지수의 개수는 8개로 N을 K^i로 나눈 값의 합과 같다!

다르게 표현하면 2의 지수의 개수는 다음과 같다.

10! = 1 × 2 × 3 ×4 × 5 × 6 ×7 × 8 × 9 × 10 → 0+1+0+2+0+1+0+3+0+1인데 조금 더 변형하면

0+1+0+1+0+1+0+1+0+1 → n/2

0+0+0+1+0+0+0+1+0+0 → n/4

0+0+0+0+0+0+0+1+0+0 → n/8 와 같다!

따라서 이런 원리로 N을 K^i로 지속적으로 나누면 N!에 포함된 K의 지수의 개수를 구할 수 있다.

 느낀 점

이해를 전혀 하지 못해서 푸는데 오래 걸렸다. 많은 분들의 해설을 읽어봤지만 전혀 도움이 되지 않았다가 어떤 분의 도움 덕분에 완벽하게 이해했다. PS의 세계에선 수학이 참 중요한 것 같다...

 코드

#include <iostream>
#include <algorithm>
using namespace std;

int n, m;
long long cnt2, cnt5;

long long func(int n, int t) {
	long long result = 0;
	for (long long i = t; i <= n;i *= t) {
		result += n / i;
	}
	return result;
}

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

	cin >> n >> m;

	cnt2 = func(n, 2) - func(n - m, 2) - func(m, 2);
	cnt5 = func(n, 5) - func(n - m, 5) - func(m, 5);
	cout << min(cnt2, cnt5);
}