c언어 2004번 조합 0의 개수 (백준)

#include <stdio.h>

long int ans[2] = {0};
int sw = 1;

void find(long int a, long int k, int key) //5와 2개수 구하기
{
	long int tmp = a/k;
	if(tmp > 0) {
		if(sw == 1) ans[key/5] += tmp;
		else ans[key/5] -= tmp;
		find(a, k*key, key);
	} return;
}

int main(void)
{ //nCr = n! / m! (n-m)! 이므로 각각의 5, 2 개수를 구한 뒤 빼주면 된다.
	long int n, m; //input
	scanf("%ld%ld", &n, &m);
	find(n, 2, 2); //n의 5 개수
	find(n, 5, 5); //n의 2 개수
	sw = 0;
	find(m, 2, 2); //m의 5
	find(m, 5, 5); //m의 2
	find(n-m, 2, 2); //n-m의 5
	find(n-m, 5, 5); //n-m의 2
	
	long int max = (ans[0] > ans[1]) ? ans[0] : ans[1]; //더 큰거
	long int gap = ans[0]-ans[1]; //2와 5의 개수의 차이
	if(gap < 0) gap *= (-1);
	printf("%ld", max-gap); //0의 개수
	return 0;
}

 

https://www.acmicpc.net/submit/2004/45767720

로그인

 

 

풀이

1) n! 의 2, 5 개수 구하는 방법

 

/*
5의 개수 구하는 법
ex) 25! = 25 * 24 * 23... 3 * 2 * 1

위의 모든 요소들을 5로 나눴을 때 나머지가 0인 것은 25 20 15 10 5로 5개이다.
위의 모든 요소들을 25로 나눴을 때 나머지가 0인 것은 25로 1개이다.
즉 25!의 5의 개수는 25를 5로 나눴을 때의 몫 25로 나눴을 때의 몫의 합이다.

그러므로, 5의 개수를 구하는 공식은
 Σ (n/5^i) (i = 1이며 1씩 증가하되, n / (5^i) > 0을 만족해야 함)이다.
 즉 2의 개수를 구하는 공식은
 Σ (n/2^i) (i = 1이며 1씩증가하되, n / (2^i) > 0을 만족해야 함)이다.
*/

n!을 풀어 헤친 다음 각각의 수마다 2, 5의 개수를 찾기엔 시간이 너무 많이 걸리기 때문에, 위의 같은 방식 또는 더 빠른 다른 방법으로 2와 5의 개수를 구해줘야 한다.

 

2) 0의 개수 구하는 방법

 

뒷자리의 0의 개수는 2의 개수 또는 5의 개수의 최솟값이다.
2 * 5 = 10 이므로 0이 1개 생긴다.

5 가 10개 있더라도 2가 3개 있으면, 0은 3개만 존재한다.