28. N!에서 0의 개수

 

    28번 문제   

 

---

    내가 풀이한 답   

 전 문제인 27번 문제와 상당히 유사하다고 생각했다. 일의 자리부터 0이 연속적으로 몇 개 있는지 알려면 2로 소인수분해 했을 때의 개수와 5로 소인수분해 했을 때의 개수가 필요하다고 생각했고 둘 중 작은 값이 0의 개수라고 생각하고 코드를 짰다. 

 

#include <stdio.h>

int arr[6];
int main(int argc, char** argv) {
	//freopen("input.txt", "rt", stdin);

	int n, i, temp, j;
	scanf("%d", &n);
	
	for(i=2; i<=n; i++){
		temp=i, j=2;
		while(j<6){
			if(temp%j==0){
				arr[j]++;
				temp /= j;
			}
			else j++;
		}
	}
	
	if(arr[2] <= arr[5]) printf("%d", arr[2]);
	else printf("%d", arr[5]);
	
	return 0;
}

 

 결과는 통과하였다.

 

 

---

    사이트의 답안   

#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
int main(){
	freopen("input.txt", "rt", stdin);
	int n, i, j, tmp, cnt1=0, cnt2=0;
	scanf("%d", &n);
    
	for(i=2; i<=n; i++){
		tmp=i;
		j=2;
		while(1){
			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) printf("%d\n", cnt1);
	else printf("%d\n", cnt2);
	return 0;
}

 

  사이트의 답은 2의 개수와 5의 개수를 따로 변수를 설정하였다. 핵심적인 논리는 2와 5의 개수를 찾는 것으로 똑같았다.