#1676: 팩토리얼 0의 개수

백준 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;
}
*/