2004번 조합 0의 개수

문제링크 : www.acmicpc.net/status?user_id=narae_dev&problem_id=2004&from_mine=1

채점 현황

 

 

<고려사항 1번>

이전1676번에서 썼던 방법은 N의 범위가 0<=N<=500이었기 때문에 같은 시간제한 아래서도 가능했으나 지금은 N의 범위가 훨씬 크기 때문에 같은 방법을 쓸 수 없다. 따라서 새로운 방법을 고안해보기로 했다.

  ex) 6C2 = (6!/(6-2)!)/1!

		인수 중 2의 개수	인수 중 5의 개수
6C2	(6*5)/(2*1)	0	1
6!	6*5*4*3*2*1	4	1
(6-2)!	4*3*2*1	3	0
2!	2*1	1	0

=> 6C2의 인수 중 2의 개수 = 6!의 인수 중 2의 개수 - (6-2)!의 인수 중 2의 개수 - 2!의 인수 중 2의 개수

 

ex) 10C4 = (10!/(10-4)!)/4!

		인수 중 2의 개수	인수 중 5의 개수
10C4	(10*9*8*7)/(4*3*2*1)	1	1
10!	10*9*8*7*6*5*4*3*2*1	8	2
(10-4)!	6*5*4*3*2*1	4	1
4!	4*3*2*1	3	0

=> 10C4의 인수 중 2의 개수 = 10!의 인수 중 2의 개수 - (10-4)!의 인수 중 2의 개수 - 4!의 인수 중 2의 개수

 

따라서, NCM의 인수 중 2의 개수를 구하려면 (N!의 인수 중 2의 개수 - (N-M)!의 인수 중 2의 개수 - M!의 인수 중 2의개수)방식을 이용해야 한다.

 

 

<고려사항 2번>

인수의 개수를 하나씩 세는 while문(1676번에서 사용한 방법)을 이용하면 너무 시간이 오래걸린다. 따라서 가능한한 while문의 반복 횟수를 줄일 수 있는 방법을 고려해야한다.

 

ex) 6!의 인수 중 2의 개수

6/2 => 몫 = 3 => 6~4까지의 인수 중 2의 개수(6,4)

3/2 => 몫 =1 => 3~2까지의 인수 중 2의 개수(2)

1/2 => 몫 =0 => 1~0까지의 인수 중 2의 개수

 

ex) 10!의 인수 중 2의 개수

10/2 => 몫 = 5 =>10~6까지의 인수 중 2의 개수(10,8,6)

5/2 => 몫 = 2 => 5~3까지의 인수 중 2의 개수(4)

2/2 => 몫 = 1 => 2~2까지의 인수 중 2의 개수(2)

1/2 => 몫 = 0 => 1~0까지의 인수 중 2의 개수 

 

=> N!의 인수 중 2의 개수를 센다면 N/2의 몫은 N~몫까지의 수들의 인수의 2의 개수이므로

몫이 1이 될때까지 반복해서 더하면 총 인수 2의 개수를 셀 수 있다. 

 

 

 

방법1. (N!의 2의 개수 - (N-M)!의 2의 개수 - M!의 2의개수)와 (N!의 5의 개수 - (N-M)!의 5의 개수 - M!의 5의개수)의 최솟값 ( 메모리 : 2016KB   시간 : 0ms ) 

#include <iostream>
using namespace std;

unsigned long count(unsigned long a, unsigned long b) {
	unsigned long c = 0;
	while (a) {
		c += a / b;
		a /= b;
	}
	return c;
}
int main() {

	unsigned long N = 0;
	unsigned long M = 0;
	cin >> N >> M;

	unsigned long count_2 = 0;
	count_2 = count(N, 2) - count(N - M, 2) - count(M, 2);
	unsigned long count_5 = 0;
	count_5 = count(N, 5) - count(N - M, 5) - count(M, 5);
	cout << ((count_2 >= count_5) ? count_5 : count_2);

	return 0;
}

 

 

방법2. 파스칼 삼각형 + 일일히 소인수분해 이용하기 => 메모리초과(N이 클경우 vector 크기가 너무 커짐)

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

int main() {

	int N = 0;
	int M = 0;
	cin >> N >> M;
	vector<int>before(N + 1,1);
	vector<int>after(N + 1,1);
	
	for (int i = 0; i <= N; i++) {
		for (int j = 0; j <= i; j++) {
			if (j == 0 || i == j) {
				after[j] = 1;
			}
			else {
				after[j] = before[j] + before[j - 1];
			}
		}
		before = after;
	}

	int temp = after[M];
	int count_2 = 0;
	int count_5 = 0;
	while (true) {
		if ((temp % 2 == 0) || (temp % 5 == 0)) {
			if (temp % 2 == 0) {
				++count_2;
				temp /= 2;
			}
			else if (temp % 5 == 0) {
				++count_5;
				temp /= 5;
			}
		}
		else break;
	}
	cout << ((count_2 >= count_5) ? count_5 : count_2);
	return 0;
}

 

 

방법3. 파스칼 삼각형 + 고려사항2번 활용 방안 => 메모리초과(N이 클경우 vector 크기가 너무 커짐)

#include <iostream>
#include <vector>
using namespace std;
unsigned long count(unsigned long a, unsigned long b) {
	unsigned long c = 0;
	while (a) {
		c += a / b;
		a /= b;
	}
	return c;
}
int main() {
	unsigned long N = 0;
	unsigned long M = 0;
	cin >> N >> M;

	vector<unsigned long> before(N + 1,1);
	vector<unsigned long> after(N + 1,1);
	for (unsigned long i = 0; i <= N; i++) {
		for (unsigned long j = 0; j <= i; j++) {
			if (i == j || j == 0) {
				after[j] = 1;
			}
			else {
				after[j] = before[j - 1] + before[j];
			}
		}
		before = after;
	}

	unsigned long count_2 = count(after[M], 2);
	unsigned long count_5 = count(after[M], 5);

	cout << (count_2 >= count_5 ? count_5 : count_2);
	return 0;
}