백준 1676번 (팩토리얼 0의 개수) c++

문제

 

문제풀이

팩토리얼은 1부터 N까지 곱하는 것을 뜻한다.

그러면 10이나 100을 곱할때 끝에 0이 생기는 것을 알 수 있다.

하지만 단순히 10이나 100의 갯수를 센다고 해서 해결이 되지 않는다.

 

5!의 경우를 생각해보자.

1 X 2 X 3 X 4 X 5 = 120

10을 곱하지 않았는데도 0이 생긴것을 알 수 있다.

2 X 5 가 존재할 때 0이 붙는 것을 생각할 수 있다.

 

그러면 2의 배수와 5의 배수를 각각 짝지어 세어주면 문제가 풀릴거 같다.

2의 배수가 5의 배수보다 숫자가 훨씬 많기 때문에 5의 배수만 세주면 될거 같지만,

아직 더 생각해야할 조건이 남아 있다.

 

만약 25의 경우는 어떨까?

25 = 5 X 5 이기 때문에 5가 2개가 필요하다 그러면 0도 2개가 필요하다는 걸 우리는 알 수 있다.

 

125의 경우에도 똑같다.

125 = 5 X 5 X 5 이기 때문에 0이 3개가 필요하다.

 

다시 정리하면,

5의 배수는 0이 1개

25의 배수는 0이 2개

125의 배수는 0이 3개

필요하다.

 

그러면 N을 받았을때 5, 25, 125로 나눈 몫들을 계산하여 모두 더하면 정답이 된다.

 

전체코드

#include <iostream>

using namespace std;

int main(){
	ios_base::sync_with_stdio(false);
    cin.tie(0);
	
    int N;

	cin >> N;

	int result = (N/5) + (N/25) + (N/125);

	cout << result << '\n';

	

	return 0;

}