[백준] 1676번: 팩토리얼 0의 개수 [C++]

 

알고리즘 분류: 수학

문제 링크: https://www.acmicpc.net/problem/1676

1676번: 팩토리얼 0의 개수

 

 

【 풀이 】

 

N! 의 뒤에서부터 처음 0이 아닌 수가 나올 때까지 0의 개수를 구하는 문제이다.

 

딱 보자마자 N! 을 구하여 저장한 후, 문자열로 변환시킨 후 맨뒤에서부터 0의 개수를 세는 알고리즘을 생각했다.그러나 N이 20 언저리를 넘어가는 순간부터 답이 이상해진다.

이는 N의 범위가 500까지이므로 파이썬이 아닌 이상 가장 큰 자료형으로도 N! 을 담을 수 없기 때문이다. (저장한 값이 중간에 잘려버림)

따라서 N! 을 소인수 분해하여 해결해야 한다.

 

N! 의 맨 뒤의 0의 개수는 소인수 분해 했을 때 2 * 5의 개수가 결정한다. 즉 2와 5 중 등장 횟수가 더 적은 쪽이 답이 된다.

그러나 소인수 분해를 해보면 알겠지만, 2의 개수가 더 많을 수밖에 없다.

이는 모든 짝수가 2의 배수이기 때문이다. 따라서 5의 횟수만 세주면 된다.

단 여기서 주의해야 할 점은 5의 거듭제곱이다.

5가 여러 번 곱해지기 때문에 이 경우에 횟수를 한번 더 카운트해주어야 한다.

이 문제의 경우 N의 범위가 500 이하이므로, 25와 125만 신경 써주면 된다.

 

 

【 코드 】

 

#include<iostream>
using namespace std;

int main(void)
{
	int cnt = 0;
	int n;
	cin >> n;
    
	for (int i = 1; i <= n; i++)
	{
		if (i % 5 == 0)		//	5의 배수일 때
		{
			cnt++;
			if (i % 25 == 0)		//	25의 배수일 때
				cnt++;
			if (i % 125 == 0)		//	125의 배수일 때
				cnt++;
		}
	}
    
	cout << cnt;
}