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

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

2004번: 조합 0의 개수

 

팩토리얼 0의 개수와 마찬가지로 소인수분해를 했을때 5의 갯수를 세어준다. 전 문제에서는 25와 125를 따로 구해주었지만 이번문제는 n의 범위가 2,000,000,000 이므로 따로 정해주지말자

 

또한 0부터 n까지의 5의 갯수, 0부터 m까지의 5의 갯수, 0부터 n-m까지의 5의 갯수를 따로 구해준뒤 마지막에 빼주도록 하자.

 

#include <iostream>
using namespace std;

int main() {
int N, M, ans = 0, ans2 = 0;
cin >> N >> M;
int k = N - M, ans3 = 0;


for (int i = 5; i <= N; i *= 5) {
ans += N / i;
}

for (int i = 5; i <= M; i *= 5) {
ans2 += M / i;
}

for (int i = 5; i <= k; i *= 5) {
ans3 += k / i;
}

cout << ans - ans2 - ans3;

return 0;
} 

 

결과는 실패 시간초과도 아니고 실패가 나온 이유를 생각해보자 찾아보니 나눗셈을 포함하고 있기 때문에 2와 5를 둘다 세주어야 하고, int형의 자료형 크기때문에 long long 자료형을 사용해야한다. 

 

int main() {
long long N, M, ans = 0, ans2 = 0;
long long five1 = 0, five2 = 0, five3 = 0;
long long two1 = 0, two2 = 0, two3 = 0;
cin >> N >> M;
long long k = N - M, ans3 = 0;

for (long long i = 2; i <= N; i *= 2) {
two1 += N / i;
}

for (long long i = 5; i <= N; i *= 5) {
five1 += N / i;
}

for (long long i = 2; i <= M; i *= 2) {
two2 += M / i;
}

for (long long i = 5; i <= M; i *= 5) {
five2 += M / i;
}

for (long long i = 2; i <= k; i *= 2) {
two3 += k / i;
}

for (long long i = 5; i <= k; i *= 5) {
five3 += k / i;
}

ans = two1 > five1 ? five1 : two1;
ans2 = two2 > five2 ? five2 : two2;
ans3 = two3 > five3 ? five3 : two3;

cout << ans - ans2 - ans3;

return 0;
}

 

하드코딩으로 그냥 경우의 수를 다 써서 계산을 했는데 또 틀렸다. 함수를 짜서 처음부터 다시 풀기로 결정

 

#include <iostream>
#include <algorithm>
using namespace std;
long long test(int num, int cnt) {
	int ans = 0;
	for (long long i = cnt; i <= num; i *= cnt) {
		ans += num / i;
	}
 
	return ans;
}
int main() {
	int n, m;
	long long two = 0, five = 0;
	cin >> n >> m;
 
	two = test(n, 2) - test(m, 2) - test(n - m, 2);
	five = test(n, 5) - test(m, 5) - test(n - m, 5);
 
	cout << min(two, five);
 
}

 

성공!! 간단한 문제인데 기초가 부족하니까 너무 어려운것 같다.

 

마지막으로 깨달은 핵심은 int와 long long을 적절하게 잘 사용하는것.