[인프런 C++] 28. N!에서 0의 갯수

🍧 문제

자연수 N이 입력되면 N! 값에서 일의 자리부터 연속적으로 0이 몇 개 있는지 구하는 프로그램을 작성하세요.

만약, 5! = 120 = 일의 자리부터 연속적인 0의 갯수는 1개이다.

만약, 12! = 479001600으로 일의 자리부터 연속적인 0의 갯수는 2개이다.

 

🍧 입력

12

 

🍧 출력

2

 

🍧 1트 (강의 풀이)

10이 얼마나 있는가? 를 확인하면 된다. 👉 10 = 2 * 5 이므로, 값을 소인수분해하여 2와 5의 갯수를 확인한다.

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

int main(void){
	//freopen("input.txt", "rt", stdin);
	
	int n, j, tmp;
	int cnt1 = 0, cnt2 = 0;
	cin >> n;
	for(int i = 2; i <= n; ++i){
		tmp = i;
		j = 2;
		
		while(true){
			if(tmp % j == 0){
				if(j == 2){
					cnt1++;
				}
				else if(j == 5){
					cnt2++;
				}
				
				tmp = tmp / j;
			}
			else{
				j++;
			}
			
			if(tmp == 1) break;
		}
	}
	
	if(cnt1 < cnt2){
		cout << cnt1;
	}
	else{
		cout << cnt2;
	}
	
	return 0;
}