[Baekjoon/백준] 2004번: 조합 0의 개수(C/C++)

단계별로 풀어보기 17단계(정수론 및 조합론) 12번 문제

https://www.acmicpc.net/step/18

정수론 및 조합론 단계

---

백준 2004번: 조합 0의 개수

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

2004번: 조합 0의 개수

---

문제 설명

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

---

입력과 출력

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

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

---

접근 방법

이번 문제는 두 정수 n과 m을 입력받아, nCm의 끝자리 0의 개수를 출력하는 문제다.

일단 nCm = n! / m!(n-m)! 이고, 이전 문제에서 말했듯 끝자리 0의 개수는 10의 약수인 2와 5의 개수 중 작은 것을 찾으면 된다. 그러므로 앞의 식에 따라 'n!에서 나오는 2의 개수 - m!에서 나오는 2의 개수 - (n-m)!에서 나오는 2의 개수'와 'n!에서 나오는 5의 개수 - m!에서 나오는 5의 개수 - (n-m)!에서 나오는 5의 개수' 중 작은 것을 출력하면 문제를 해결할 수 있다.

---

코드

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

long long findNum(int cal, int num) {
	long long count = 0;

	for (long long i = num; i <= cal; i *= num)
		count += cal / i;

	return count;
}

int main(int argc, char *argv[]) {
	int n, m;

	cin >> n >> m;

	long long twoCount = findNum(n, 2) - findNum(m, 2) - findNum(n - m, 2);
	long long fiveCount = findNum(n, 5) - findNum(m, 5) - findNum(n - m, 5);

	cout << min(twoCount, fiveCount) << endl;

	return 0;
}

---

결과

백준 제출 결과