2004번: 조합 0의 개수

문제:

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

입력:

첫째 줄에 정수 n, m (0≤m≤n≤2,000,000,000, n≠0)이 들어온다.

풀이:

• 이 문제를 풀기 위해서는 10이 몇개 나올 수 있는지 세면 끝자리 0의 개수를 알 수 있다. 따라서, 2와 5의 짝이 몇개 만들어 질 수 있는지 구하면 답이 나온다.
• 5의 개수와 2의 개수를 세는 방식은 똑같다. 쉽게 설명하기 위해서 5를 셀 경우만 설명하겠다. ${n \choose r}$은 $n!\over{r!(n-r)!}$이기 때문에 n!에서 5의 개수를 세어 더해주고 r!과 (n-r)!에서는 나눗셈이므로 세어 빼주면 된다. n!에서 5의 개수를 세는 방법은 5의 제곱들을 나눠주면서 5의 총 개수를 세어 주는 방법이다. 자세한 설명은 비슷한 문제인 #1676: 팩토리얼 0의 개수에서 🔍돋보기 부분에서 설명 되어 있다.
• 위와 똑같은 방식으로 r!과 (n-r)!에서 5의 개수를 세어주고 빼주면 된다. 2의 개수도 똑같은 방식으로 풀어주면 된다.
• 마지막으로 2와 5의 개수중 최솟값이 2와 5가 만들어질 수 있는 짝의 개수이므로 최솟값을 출력 해준다.

⚠️ 이 문제를 풀 때 주의 해야 될 점은 개수를 확인할 때 쓰는 two_multiple, five_multiple값이 long long이어야 되는 것이다. 그 이유는 2,000,000을 안넘는 n과 m은 int형인 것이 상관 없는데 two_multiple, five_multiple은 n과 m이 2,000,000과 같은 큰 수 인 경우에는 2, 5를 곱하였을 때 값이 int형이 담을 수 없는 값만큼 커지기 때문에 long long으로 설정해야 overflow가 발생하지 않는다.

아래에서 모든 자료형을 long long으로 선언한 이유는 어짜피 int값과 long long값을 연산을 하게 되면 int값이 자동으로 long long으로 변환 되기 때문에 몇개만 int형으로 선언하는게 의미가 없기 때문이다.

코드:

#include <iostream>

using namespace std;

int main(){
	long long n, m, num_two = 0, num_five = 0, two_multiple=2, five_multiple = 5;
	//입력 
	cin >> n >> m;
	//---------5의 개수--------------
	//n에 있는 5의 개수 더해주기
	while(n/five_multiple){
		num_five+=n/five_multiple;
		five_multiple*=5;
	}
	//5의 배수 초기화
	five_multiple = 5;
	//m에 있는 5의 개수 빼주기
	while(m/five_multiple){
		num_five-=m/five_multiple;
		five_multiple*=5;
	}
	//5의 배수 초기화
	five_multiple = 5;
	//n-m에 있는 5의 개수 빼주기
	while((n-m)/five_multiple){
		num_five-=(n-m)/five_multiple;
		five_multiple*=5;
	}
	//---------2의 개수--------------
	//n에 있는 5의 개수 더해주기
	while(n/two_multiple){
		num_two+=n/two_multiple;
		two_multiple*=2;
	}
	//2의 배수 초기화
	two_multiple = 2;
	//m에 있는 2의 개수 빼주기
	while(m/two_multiple){
		num_two-=m/two_multiple;
		two_multiple*=2;
	}
	//2의 배수 초기화
	two_multiple = 2;
	//n-m에 있는 2의 개수 빼주기
	while((n-m)/two_multiple){
		num_two-=(n-m)/two_multiple;
		two_multiple*=2;
	}
	//두개의 값중 최솟값 출력
	cout << min(num_two, num_five); 
}