BOJ 1676 - 팩토리얼 0의 개수

문제 링크

문제#

N!에서 뒤에서부터 처음 0이 아닌 숫자가 나올 때까지 0의 개수를 구하는 프로그램을 작성하시오.

입력#

첫째 줄에 N이 주어진다. (0 ≤ N ≤ 500)

출력#

첫째 줄에 구한 0의 개수를 출력한다.

풀이#

팩토리얼 끝의 0은 10 = 2 × 5가 몇 번 만들어지는지에 따라 결정된다. 2는 항상 5보다 많이 나오므로, 결국 N! 안에 5가 몇 개 들어 있는지만 세면 된다.

그래서 N / 5 + N / 25 + N / 125 ...처럼 5의 배수, 25의 배수, 125의 배수를 차례로 더하면 정답이 나온다. 코드는 이 원리를 그대로 사용해 불필요한 큰 수 계산 없이 끝자리 0의 개수만 바로 구한다.

코드#

#include <iostream>
using namespace std;
 
int main() {
 
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
 
	int N;
	cin >> N;
 
	int count = 0, n;
 
	while (N--) {
		n = N + 1;
		while (n >= 5) {
			if (n % 5 == 0) {
				count++;
				n /= 5;
			}
			else
				break;
		}
	}
 
	cout << count << '\n';
 
	return 0;
}

복잡도#

• 시간 복잡도: $5$의 거듭제곱을 나누며 세므로 $O(\log N)$이다.
• 공간 복잡도: 상수 개수의 변수만 사용하므로 $O(1)$이다.

마무리#

팩토리얼 끝의 0은 10 = 2 × 5가 몇 번 만들어지는지에 따라 결정된다.