팩토리얼 0 의 개수 _ 백준 1676

이번 문제는 팩토리얼과 관련된 문제이다.

---

팩토리얼은 기본적으로 큰 수이기 때문에, 일일히 확인하는 방식은 옳지 않다.

 

맨 처음으로 생각한건 10으로 나눴을때 나머지가 0인걸 생각했는데,

10은 2와 5의 곱셈으로 이루어지고, 2의 배수보다는 5의 배수가 더 적으니 5의 배수인 것의 수를 세서 0의 개수를 확인할 수 있을 것 같다고 생각했다.

 

그래서 5의 배수 , 25의 배수, 125의 배수일때 수를 세는 것으로 알고리즘을 짰다. (125까지인 이유는 입력이 500 이하의 값이기 때문에!)

#include <iostream>
#include <cstdio>
using namespace std; 
int main(void)
{
	int a;
	int result = 0;
	scanf("%d", &a);
	for (int i = 2; i <= a; i++)
	{
		if (i % 5 == 0)
			result++;
		if (i % 25 == 0)
			result++;
		if (i % 125 == 0)
			result++;
	}
	
	printf("%d", result);
	return 0;
}

그런데, 코드플러스 강의를 듣고 다시 보니까 좀더 코드가 짧은 방식으로도 문제를 풀 수 있더라... (위의 알고리즘도 맞음! 다만 아래 코드가 더 짧고, 좋은 것 같으므로 같이 적어본다.

int main(void)
{
    int ans = 0;
    int n;
    scanf("%d", &n);
    for (int i =5; i<= n; i*= 5){
        ans += n/i;
    }
    
    printf("%d", ans);
    return 0;
}

둘다 5의 배수를 활용하는 것은 같지만, 어떻게 더 효율적으로 코드를 짤 수 있는가가 달라지는 것 같다.. 

 

생각한 아이디어를 더 효율적으로, 코드로 구현하는 방법을 계속 공부해야지..!