백준 2004. 조합 0의 개수

백준 2004. 조합 0의 개수

nCm 조합을 구하고, 끝자리 0의 개수를 구하는 문제

백준 1676. 팩토리얼 0의 개수의 응용 문제이다

1. 간단 설명

---

첫째 줄에 정수 n, m (0 <= n, m <= 2,000,000,000, n != 0) 이 주어진다

nCm의 끝자리 0의 개수를 출력

2. 문제 분석

---

주의사항

• n과 m이 20억이나 되므로 정수형 오버플로우에 주의

• 시간제한은 2초이므로 약 2억번 수행 가능

풀이

1. 완전 탐색 이용
   • 조합 공식 n!/(n-m)!m! 을 factorial 함수를 구현하여 돌리면 무조건 오버플로우 발생으로 실패
2. 2와 5의 개수를 구해서 0의 개수 구하기
   • 이전 문제 ‘백준 1676. 팩토리얼 0의 개수’의 응용 버전
   • 간단히 위 문제를 설명하면 500이하의 N!에서 처음 0이 아닌 숫자가 나올때까지 0을 구하는 문제
   • N!를 소인수 분해하여 2와 5의 개수를 구한뒤, 둘 중 작은 값을 취하면 0의 개수를 구할 수 있는 문제였음 - 이를 응용하여 ‘N! 에서 K의 지수의 개수를 구하는 방법’

N을 K^i로 나누었을 때, N!에서 K의 지수를 구할 수 있다

• 예를들어 N = 5, K = 2인 경우

N! = 1 * 2 * 3 * 4 * 5

2로 나눠서 0이 되는 수들의 개수 = 2, 4 이므로 2개

4로 나눠서 0이 되는 수들의 개수 = 4 이므로 1개

2는 총 3개가 존재한다

• 이번엔 N을 좀 크게 예를들어 N = 25, K= 2인 경우

25! = 1 * 2 * 3 * ... * 24 * 25 로 표현할 수 있다

25 / 2 = 12개 (2,4,6,…,24) 25 / 2^2 = 6개 (4,8, 12, …, 24) 25 / 2^3 = 3개 (8, 16, 24) 25 / 2^4 = 1개 (16)

12 + 6 + 3 + 1을 더하면 총 22, 25!에 2는 22개 존재한다

N = 25, K = 5인 경우 마찬가지로

25 / 5 = 5(5,10,15,20,25) 25 / 5^2 = 1 이므로 25!에 5는 총 6개가 존재한다

• 이런식으로 N!과 (N-M)!M!의 2와 5의 개수를 구한뒤, 식을 정리하면 된다

알고리즘

1. N, M을 입력받는다
2. nCm의 5의 개수를 구한다
	2-1. N!의 5의 개수 구하기
	2-2. N-M! 의 5의 개수 구하기
	2-3. M!의 5의 개수 구하기
	2-4. N!의 5의 개수에서 (N-M)!M! 의 개수 빼기
3. 2의 과정과 유사하기 2의 개수를 구한다
4. 둘 중 작은 값을 선택하면 0의 개수가 나온다(2와 5의 곱으로 10을 만들기 때문)
5. 출력 후 종료

3. 소스코드

---

#include <iostream>

using namespace std;

// N!에서 K의 개수를 구하는 함수 
int counting(int n, int k) {
	int cnt = 0;

	for (long long int i = k; i <= n; i = i * k) {
		cnt += n / i;
	}

	return cnt;
}


int main() {
	int N, M; // N, M <= 20억, int +-21억

	cin >> N >> M;

	int five = counting(N, 5) - (counting(N - M, 5) + counting(M, 5)); 
	int two = counting(N, 2) - (counting(N - M, 2) + counting(M, 2)); // 합은 21억을 넘지 못함

	cout << min(five, two); // 둘중 작은 값을 선택 
	return 0;
}

배운점

1676번에서 0을 구하는 방법은 쉽게 유추할 수 있었으나,

이를 응용한 0의 개수를 구하는 버전에서는 쉽게 생각해내지 못했다

특히 N!를 이용해 K^i의 개수를 구하는 방법은 풀이를 봐도 직관적으로 이해가 되지 않아

코드를 디버깅하면서 출력해보고 이해했다

참조

https://velog.io/@ledcost/백준-1676-파이썬-팩토리얼-0의-개수-실버4-정수론