백준 알고리즘 2004번: 조합 0의 개수 [C++]

문제 출처: www.acmicpc.net/problem/2004

2004번: 조합 0의 개수

1. 코드

#include <iostream>

using namespace std;

long long d2(long long N)		//2의 개수
{
	long long cnt = 0;
	for (long long i = 2; i <= N; i *= 2)
		cnt += N / i;
	return cnt;
}

long long d5(long long N)		//5의 개수
{
	long long cnt = 0;
	for (long long i = 5; i <= N; i *= 5)
		cnt += N / i;
	return cnt;
}

int main(void)
{
	long long n, m;
	cin >> n >> m;
	cout << min(d5(n) - d5(m) - d5(n - m), d2(n) - d2(m) - d2(n - m));	//조합 공식
}

(실행)

2. 풀이

문제를 살펴보면 두 수를 입력받고 조합의 공식에서 도출된 값에서 0의 개수를 구하는 문제이다. 해당 조합의 공식은 n!/(m!×(n - m)!)이다.

long long n, m;
cin >> n >> m;

우선 두 수를 입력받는다.

cout << min(d5(n) - d5(m) - d5(n - m), d2(n) - d2(m) - d2(n - m));	//조합 공식

그리고 해당 값을 출력하는데 min은 최소 값을 구하는 것이다. d2는 해당 수를 인수분해할 때 나오는 2의 개수이고, d5는 5의 개수이다. 그런데 2 * 5 = 10이다. 그렇다면 2와 5 두 개가 존재해야 조합의 공식에서 도출된 값에서 0이 생기기 때문에 2와 5의 개수 중 가장 작은 것을 출력하는 것이다.

long long d2(long long N)		//2의 개수
{
	long long cnt = 0;
	for (long long i = 2; i <= N; i *= 2)
		cnt += N / i;
	return cnt;
}

long long d5(long long N)		//5의 개수
{
	long long cnt = 0;
	for (long long i = 5; i <= N; i *= 5)
		cnt += N / i;
	return cnt;
}

d2와 d5를 먼저 살펴보면 반복문을 이용하여 아주 손쉽게 구할 수 있다. 기존의 for 문의 증감식은 i++였다. 하지만 이렇게 반복하면 많은 시간이 걸려서 시간 초과가 발생하고 i += 2 or i += 5를 하여도 시간 초과가 발생한다. 그래서 i *= 2 i *= 5를 사용해서 빠르게 구할 수 있게 된다.

3. 느낀 점

처음에는 이전 문제인 팩토리얼 0의 개수에서 해결한 방법과 동일하게 해결하려고 했지만 시간 초과가 발생하고 증감식을 이용하여 i += 2, i += 5를 사용하여 하는 방법도 시간 초과가 발생하였다. 그래서 생각한게 배열을 이용한 메모제이션이 있었는데 해당 방법은 이 문제에서 사용이 불가능했다. 왜냐하면 입력하는 값이 최대 2000000000인데 이 만큼의 배열을 생성하는 것은 불가능하기 때문이다. 결국 방법을 알지 못하여 검색하여 해당 방법을 알게 되었다.