백준 1676 팩토리얼 0의 개수 - C언어 논리

N! 를 1의 자리부터 시작해 처음 0보다 큰 숫자가 나올 때까지 0을 센다.

가령 5! 이면 5*4*3*2*1 = 120 이므로 처음 0이 아닌 숫자 2가 나오기까지 0이 한 개 나온다.

6! 이면 720 이므로 한 개, 7! 이면 5040 이므로 한 개다.

이는 9!까지 유지되다가 10!에 두 개로 바뀌게 된다.

 

우리는 0의 개수만 관심 있으므로 나름의 논리를 찾아보면 된다.

 

임의의 자리의 수가 0이라면 어떤 수를 곱해도 0이 아닌 수가 될 수 없다.

 

가령 10이 있다면 어떤 수를 곱해도 0은 변하지 않는다.

그러므로 0이 늘어날 수 있는 경우는 10을 곱할 때 밖에 없다. (100)

 

물론 1020 과 같이 중간에 0이 있는 경우는 바뀔 수 있다. (예시: 1020 * 6 = 6120)

하지만 연속으로 0이 있는 경우에는 그 어떤 수를 곱해도 같은 결과가 나온다.

 

조금 더 생각해보면, 24 * 25 는 몇 개의 0을 얻을 수 있을까?

24 = 2^3 * 3 이고 25 = 5^2  이므로 10이 두 개 있는 경우와 같으므로 2개의 0을 얻을 것으로 기대된다.

실제 계산해보면 600 이므로 2개가 나옴을 확인할 수 있다.

 

즉 결론적으로, 10을 몇 개나 곱했냐에 따라 0이 연속으로 나올 수를 구할 수 있다는 뜻이 된다.

 

그러므로 N팩토리얼을 직접 구할 필요없이 (실제로 N이 500까지 long long 을 써도 불가능하다...)

우리가 할 것은 곱할 수를 소인수분해하여 2와 5가 몇 개씩 있는지 계산하고, 10으로 몇 개나 조합이 가능한지

출력하는 것 뿐이다.

 

전체코드

#include <stdio.h>
int N;
int solve() {
	//2 * 5 가 나올때마다 0이하나씩 늘어남
	int ret = 0;
	int two = 0;
	int five = 0;
	for (int i = 1; i <= N; i++) {
		int num = i;
		for (;;) {
			if (num % 2) break;
			num /= 2;
			two++;
		}
		for (;;) {
			if (num % 5) break;
			num /= 5;
			five++;
		}
	}
	if (two > five) return five;
	else return two;

}

int main() {
	scanf("%d", &N);

	int ans = solve();
	printf("%d", ans);
}