백준 2004번

2004번

👍 문제

$n \choose m$의 끝자리 $0$의 개수를 출력하는 프로그램을 작성하시오.

👍 입/출력

입력 : 첫째 줄에 정수 $n$, $m$ ($0 \le m \le n \le 2,000,000,000$, $n \ne 0$)이 들어온다.
출력 : 첫째 줄에 $n \choose m$의 끝자리 $0$의 개수를 출력한다.

👍 내 마음대로 해설

0이 1개로 끝나는 숫자 10을 예로 들어보자

각각 2 1개, 5 1개이다.


0이 2개로 끝나는 숫자 100을 예로 들어보자

각각 2 2개, 5 2개이다.


0이 3개로 끝나는 숫자 1000을 예로 들어보자

각각 2 3개, 5 3개이다.


그렇다면 n!의 끝의 0 개수를 세기 위해서는
무식하게 n!를 곱해서 저장하는 것이 아니라 (n이 2,000,000,000이면 결과가 너무나도 커짐)
n! 안에 들어있는 2와 5 개수 중 minimum인 값을 구하면 해당 0 개수가 나오는 것이다.

그러면

요 놈은 n!에 들어있는 0의 자리 개수가 k!, (n-k)! 각각에 들어있는 0의 자리 수만큼 없어질 것이기에
n!,k!,(n-k)!의 각각 2와 5의 개수를 세준 뒤에 최종적인 2와 5의 개수를 구하고
그 두 개의 개수 중 더 작은 것을 고르면 답이 나오는 것이다.

그렇다면 왜 아래 코드와 같이

for (long long i = 2; i <= n; i *= 2)
		v[0] += n / i;

식으로 n!의 2의 개수를 구하였나

25!의 2의 개수를 구하여야하는 상황이 있다고 가정하자.

처음 i=2일 때 25/2를 하면 (type이 long long이므로) 12가 저장된다.
이 뜻은 1~25 중에 2 하나를 약수로 가지고 있는 숫자가 12개(2,4,...24)라는 뜻이다.

두번째로 i=2*2일 때 25/2*2를 하면 6이 저장된다.
이 뜻은 1~25 중에 4를 약수로 가지고 있는 숫자가 6개(4,8,...24)라는 뜻이다.

세번째로 i=2*2*2일 때는 8을 약수로 가지고 있는 숫자가 3개(8,16,24),
마지막으로 i=2*2*2*2일 때는 16을 약수로 가지고 있는 숫자가 1개(16)이다.

그러면 이 개수들을 전부 더해주면 25!의 2의 전체 개수가 나오지 않겠는가?!

실수 조심
여기서 조심해야할 점은 내가 실수했던 부분인데
i=2*2일 때 나오는 숫자들은 각각 2의 개수가 2개씩이니까
더할 때도 (4를 약수로 가진 숫자의 개수)*2를,
마찬가지로 (8을 약수로 가진 숫자의 개수)*3을 해야되지 않느냐인데
2나 3을 곱해줄 필요는 전혀 없다.

예시로 4를 약수로 가지는 4,8,12,16,20,24는
2를 약수로 가지는 숫자 개수에 이미 한 번 포함되어 더해졌기 때문에
($2$약수 개수) + ... ($2^n$ 약수 개수)만 해주면
n!의 전체 2의 개수의 정답이 나오게 된다.

👍 c++ 정답 코드

#include <bits/stdc++.h>
using namespace std;

vector<long long> calc(long long n) {
	vector<long long> v(2);
	for (long long i = 2; i <= n; i *= 2)
		v[0] += n / i;
	for (long long i = 5; i <= n; i *= 5)
		v[1] += n / i;

	return v;
}

int main() {
	long long n,k;
	long long cnt2(0), cnt5(0);
	vector<vector<long long>> ans(3);
	cin >> n >> k;

	ans[0] = calc(n);
	ans[1] = calc(k);
	ans[2] = calc(n-k);
	cnt2 = ans[0][0] - ans[1][0] - ans[2][0];
	cnt5 = ans[0][1] - ans[1][1] - ans[2][1];

	cout << min(cnt2,cnt5) << '\n';
}