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

 

시험 끝나고 오랜만에 백준을 풀었다. 시험기간엔 솔직히 풀 시간이 없어서 항상 아쉽기도 하고 풀더라도 글쓰기가 귀찮아서 안쓰는 것 같다..

 

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

2004번: 조합 0의 개수

 

문제

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

입력

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

 

출력

첫째 줄에  끝자리 0의 개수를 출력한다.

예제 입력 1

25 12

예제 출력 1

2

 

풀이

이 문제는 '조합'이 무엇인지 부터 알아야한다. 뭐.. 고등학교를 나온 사람이라면 누구나 알고 있을테지만, 다시 정리해보겠다. 

조합이란 '서로 다른 n개에서 r개를 고르는 상황'이다. 단, 이때 순서를 고려하지 않는다. a, b, c, d, e 가 있다고 가정했을 때 2개를 뽑는다면 a먼저 뽑고 e가 나오던, e 먼저 뽑고 a가 나오던 같은 상황이라는 것이다. 

서로 다른 n개에서 r개를 고르는 상황을 아래 기호처럼 표시하고 조합(Combination)이라고 부른다. 

 

위에 이미 식이 적혀있으니 우린 이걸 이용만 하면 된다. 

 

가장 쉽게 생각할 수 있는 풀이는 직접 nCr을 구해서 마지막 0의 개수를 세는 것이다. 하지만, 입력값은 n이 약 20억이기 때문에 가뿐하게 오버플로우가 발생할 것이다. 그래서 생각할 수 있는 것이 5의 개수를 세는 것이다. 이 방식은 팩토리얼 과정에서 마지막 0을 구할 때 사용한 방법인데 맨 뒤 0의 개수는 10이 곱해진 숫자라는 것을 알 수 있고, 2와 5의 개수 중 더 작은 것을 고르면 된다. 하지만, 5의 개수가 2의 개수보다 훨씬 적기 때문에 대체적으로 5의 개수를 세면 0의 개수가 나온다. 그래서 그런 식으로 코드를 짜보았다. 

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

int main()
{
	//nCm 을 구하자.
	int n, m;
	cin >> n >> m;
	int cnt1 = 0, cnt2 = 0;
	
	// n! / (n-m)! 에 들어있는 5의 개수 구하기
	for (int i = n; i > m; i--) {
		int k = i;
		while (k % 5 == 0) {
			cnt1++;
			k /= 5;
		}
	}

	for (int i = m; i > 0; i--)
	{
		int k = i;
		while (k % 5 == 0) {
			cnt2++;
			k /= 5;
		}
	}

	printf("%d\n",cnt1 - cnt2);


	return 0;

}

 

하지만, 결과는 '틀렸습니다'가 나왔다. 이 말은 5의 개수가 2의 개수보다 항상 많지 않음을 알 수 있다. 의외로 쉽게 반례를 찾을 수 있었다. 5C1을 생각해보자. 5C1 = 5이다. 5의 개수는 1개 2의 개수는 0개이다. 그래서 5의 개수로 생각하면 1이 나와 오답이 생긴다. 

 

그래서 두번째로 생각한 것이 그냥 5의 개수와 2의 개수를 모두 구해서 더 작은 것으로 취하는 방법이었다. 

#include<iostream>


int main()
{
	int cnt5_1 = 0, cnt2_1 = 0;
	int cnt5_2 = 0, cnt2_2 = 0;
	int n, m;
	std:: cin >> n >> m;

	for (int i = n; i > (n-m); i--)
	{
		int k = i;
		while (k % 5 == 0)
		{
			if ((m == 1 || (n - m) == 1) && i == n)
				break;
			cnt5_1++;
			k /= 5;
		}
	}
	for (int i = m; i > 0; i--)
	{
		if (cnt5_1 == 0)
			break;
		int k = i;
		while (k % 5 == 0)
		{
			cnt5_2++;
			k /= 5;
		}
	}
	int a = cnt5_1 - cnt5_2;
	int b = cnt2_1 - cnt2_2;
	printf("%d" ,a);
}

이 코드의 결과는 '시간초과'가 나왔다. 나도 코드를 짜면서 걱정했던 부분이긴 한데 2의 개수를 세는 과정에서 너무나도 많은 시간을 소요하고 있다. 결국 지금 내가 생각하고 있는 알고리즘으로는 풀 수 없다는 것이고 개수를 세는 새로운 방법을 알아야했다. 

그래서 방법을 찾아다니던 중 아래 질문 글을 발견하게 되었다. 

https://www.acmicpc.net/board/view/84716#comment-137720

글 읽기 - 풀이에 의문이 생겨서 질문합니다.

n!=n*(n-1)*(n-2)*...*5*4*3*2*1
n!은 1부터 n까지의 모든 정수를 곱한 것과 같죠.
여기서 소인수 5가 몇 번 곱해졌느냐를 구해야 하는데
5의 배수가 곱해지는 간격은 5입니다.
5 10 15 20 25 30 ...
여기서 5의 배수가 곱해진 횟수는 n을 5로 나눈 몫으로 알 수 있죠. 그걸 더하고
근데 5의 배수 중에서도 5가 두 번 곱해진 수가 있는데 그게 25의 배수죠.
25 50 75 100 125 150 ...
25의 배수가 몇 번 곱해졌냐도 n을 25로 나눔으로써 알 수 있죠.
마찬가지로 5가 세 번 곱해진 125의 배수(125, 250, 375, ...)가 몇 번 곱해졌는가도 125로 나눔으로써 알 수 있고
5의 배수에 25의 배수가 포함되어있으니까
n//25에 2를 곱할 필요 없이
(n//5)+(n//25)+(n//125)+... 이런 식으로 더해나가면
소인수분해했을 때의 5의 지수를 구할 수 있습니다.
꼭 5에만 해당되는 얘기는 아니고
2, 3, 7, 11 등도 n!에 몇 번 곱해져있는지는
n//2+n//4+n//8 . . . 이렇게 더하면 알 수 있습니다.
2는 안 세는 이유는 팩토리얼 뒤에 0이 붙으려면 2랑 5가 곱해져야 하는데
2는 두 칸 간격으로 곱해지니까 5에 비해 넘치도록 많아서
5만 세어도 풀리는거죠.

위 글은 팩토리얼 문제에서 시간초과를 겪으셔서 질문한 분에 담긴 답글이다. 와.. 이 글을 읽고 소름이 돋았다. 진짜 세상에는 똑똑한 분들이 많고 아직 배워갈 것이 많다는 것을 느꼈다. 

결론적으로 말하자면 n!에 k가 몇 번 곱해져 있는지는 (n//k)+(n//k^2)+(n//k^3) ... 이 된다는 것이다. 

52을 예로 들어보자. 32!에 5가 몇 번 들어가는지 구하고 싶으니 일단 5의 배수가 될 수 있는 것들을 골라보겠다.

5 10 15 20 25 30 35 40 45 50 => 10개 즉, 52//5의 값이 5의 배수의 개수이다.

하지만, 25와 50의 경우 5가 하나씩 더 들어가있다. 그 이유는 50이 25의 배수이기 때문이다. 이런 수들이 몇 개 있는지 골라내려면 추가적으로 52//25를 하면 된다. 그럼 2가 나온다. 

그래서 52//5 + 52//25 = 12개니까 52!의 5의 개수는 12개가 된다. 

 

이 방법을 쓰면 굉장히 시간복잡도가 준다. 그래서 2의 배수 계산도 가볍게 할 수 있다. 말로 이해가 잘 안되는 분들을 위해 함수 형태로 코드를 만들었다. 

void getnumber(unsigned long k, int* count, unsigned long n)
{
	unsigned long tem = k;
	while (1)
	{
		if ((n / k) == 0)
			break;
		*count += (n / k);
		k *= tem;
	}
}

n!안에 k가 몇 개 들어가있는지 살펴보는 함수이다. 개수는 count로 반환된다. 

이렇게 만든 최종코드는 아래와 같다. 

#include <iostream>


void getnumber(unsigned long k, int* count, unsigned long n)
{
	unsigned long tem = k;
	while (1)
	{
		if ((n / k) == 0)
			break;
		*count += (n / k);
		k *= tem;
	}
}

int main()
{
	unsigned long n, m;
	std::cin >> n >> m;

	if (m > (n / 2))
		m = n - m;
	int cnt2_1=0, cnt5_1=0;
	int cnt2_2=0, cnt5_2=0;

	//분자 : n!
	getnumber(2, &cnt2_1, n);
	getnumber(5, &cnt5_1, n);
	
	//분모 : m!(n-m)!
	getnumber(2, &cnt2_2, m);
	getnumber(2, &cnt2_2, (n - m));
	getnumber(5, &cnt5_2, m);
	getnumber(5, &cnt5_2, (n - m));


	int a = cnt2_1 - cnt2_2;
	int b = cnt5_1 - cnt5_2;
	printf("%d",(a > b) ? b : a);
}

주의할점은 k를 int 형이 아닌 long 형으로 해결해야하는 것이다. 이것 때문에 30분을 날렸다...

 

깔끔하게 완료~