1676 - 팩토리얼 0의 개수

1. 문제 이해

입력한 팩토리얼의 뒤부터 0의 연속되는 0의 갯수를 찾는 문제이다

2. 문제 해결

처음 나는 이 문제를 보고 이런 생각을 하였다

 

팩토리얼을 만들고 나머지 10을 해서
0이 아닐 때까지 세보면 된는거 아닌가?

 

 

그런데 이걸로 안되는 이유가 한두가지가 아니였다.

• 길이

길이가 안된다 문제에 500!까지 나오는데 이는 longlong으로 담을 수도 없는 량이다.

• 시간

곱하는 건 괜찮을 수 있어도 기본적으로 자리 수가 너무 많아 나머지 10을 계속 하게되면 테스트 시간안에 끝낼 수 없다.

 

이러한 문제로 해결이 불가능하단걸 깨닳고 아무리 생각해도 다른 방식이 생각나질 않았다.

결국 혼자의 힘으로 해결하는 것은 포기하고 인터넷에 검색을 해봤다.

 

어려 사람의 해결법을 보고 제일먼저 꺠닳은 것이 있다.

공부를 좀 더 열심히 하자였다.

 

다른 사람의 해결 방법은 의외로 간단했다

 

뒷자리가 0이 나오는 수는 10이다.
이는 소인수 분해를 하게되면 2 x 5가 된다.
즉, N! 계산중에 있는 2 x 5를 찾는다.

이거였다

 

0이 1개라도 생성되는 N은 5이다 5도 계산을 보면 5x4x3x2x1 5x2가 들어간다.

여기서 2는 여러 곳에 사용되어 당연하게도 5보다 많을 수 밖에 없다.

고로 우리는 N!에서 들어가는 5의 겟수를 새면 되는다는 뜻이다.

또한 5의 제곱인 25의 배수와 같은 경우도 추가하여 계산하는 거였다

 

3. 소스 코드

#include<iostream>

using namespace std;

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	int n;
	cin >> n;
	cout << (int)(n / 5) + (int)(n / 25) + (int)(n / 125);
}

 

---

결국 정말 짧은 코드였지만 풀이를 인터넷을 보고 해결했다는 점에서 반성해야될거같다.

다음 부터는 좀 더 생각해보고 스스로의 힘으로 풀어봐야겠다 생각했다.

또한 기초 지식이 부족하다 생각되어 공부를 좀 더 빡세게 해야겠다 생각했다.