#1676: 팩토리얼 0의 개수

문제:

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

입력:

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

풀이:

이 문제를 풀 때 주의 해야 할 점은 팩토리얼을 다 구한 뒤 0의 개수를 구하는 것이 아닌 팩토리얼을 구성하는 숫자들을 확인하면서 0의 개수를 찾는 것이다. 왜냐하면 N이 최대 500인데 이때 500!의 값은 그 어떤 자료형에 담을 수 있는 크기가 아니기 때문이다.
따라서 우리는 그 숫자가 약수로 5를 몇개 갖고 있나 확인할 것이다. 왜냐하면 2 곱하기 5는 결국 0 한개를 의미 하는 것과 똑같기 때문이다. 2의 개수를 안 세는 이유는 어짜피 5의 개수가 2의 개수 보다 현저히 적을 것이기 때문에 5의 개수만 세면 짝으로 10을 만들기 위한 2는 충분하기 때문이다.
범위가 0부터 500까지 이므로 while문에서 입력값을 1씩 빼주면서 5로 나누어질 때, 25로 나누어질 때, 125로 나누어질 때 각각 1, 2, 3을 답에 더 해주면 풀 수 있다.

🔍 스터디 하는 친구를 통해 이 문제를 풀는 훨씬 쉬운 방법을 알았다. 바로 정답은 입력값/5+입력값/25+입력값/125인 것이다. 이게 성립이 되는 이유는 위의 이유가 똑같지만 굳이 모든 값을 일일이 확인 안해도 그 숫자를 5로 나눔으로써 그 숫자까지 도달하는데 얼마나 많은 5가 필요한지 가르쳐 준다. 만약에 25의 배수인 경우에는 5가 그만큼 한번 더 있다는 것이니 한번 더 더해줌으로써 두번 세주는 것과 같은 효과가 생긴다. 이렇게 풀면 굳이 O(N)의 복잡도를 가진 연산을 할 필요가 없다.

코드:

#include <iostream>

using namespace std;

int main(){
	int n, answer = 0;
	//입력
	cin >> n;
	//n에서 하나씩 빼면서 5를 약수로 몇개 갖고 있는지 확인 
	while(n){
		if(!(n%125)) answer+=3; //5^3이므로 +3 
		else if(!(n%25)) answer+=2; //5^2이므로 +2
		else if(!(n%5)) answer+=1; //5^1이므로 +1
		n--;
	}
	//출력 
	cout<<answer;
}
/* 훨씬 간단한 답
int main(void){
    int num; 
    cin >> num;
    cout << num/5 + num/25 + num/125;
}
*/