[백준] 3474 교수가 된 현우 C++

https://www.acmicpc.net/problem/3474

 

---

접근 

아이디어적인 문제라고 생각한다. 안 풀어 보면 맞추기 힘들거 같은...

우선 5600에서 0의 개수를 구해야한다. 지금은 2개라는 것을 알 수 있는데 한번 쪼개보자.
5600 = 56 * 10 * 10 = 56 * (2 * 5) * (2 * 5)이다.

5600에서 0의 개수는 10의 개수에 따라 결정이 된다는 것을 알 수 있고 10의 개수는 2와 5의 개수로 결정이 된다는 것을 알 수 있다.

어떤 수 n에서 2의 개수가 7개 5의 개수가 3개라면 10은 3개가 나오게 된다. 7, 3 중에 최소값이 10의 개수가 된다.

 

5!을 예로 들면 

1 2 3 4 5에서 2의 배수의 개수는 5 / 2 => 2개, 5의 배수의 개수는 5 / 5 => 1개 

min(2, 1) => 1이다. 즉 0의 개수는 1개가 된다.

 

5를 2로 나누었는데 왜 2의 배수의 개수가 나오는 것일까?

1~100까지에서 2의 배수의 개수를 구한다면 보통 50이라고 알 수 있을 것이다. 2*1, 2*2, 2*3..., 2*50

1~100까지에서 7의 배수의 개수를 구하면 7*1, 7*2, 7*3...7*13, 7*14(98)이다. 즉 100을 7로 나누었을 때 몫이 7의 배수의 개수가 된다.

주의할 점은 배수의 개수를 모두 더해주어야한다.
4는 2*2이기때문에 10!에서 1 2 3 4 5 6 7 8 9 10 까지 있을 때 10/2 + 10/4 + 10/8 을 모두 더해주어야한다. 
즉 2의 제곱수를 입력받은 수 n까지 다 나누어 주어야한다.

---

코드

#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
using ll = long long;

int n, a;

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	cin >> n;
	for (int i = 0; i < n; ++i)
	{
		cin >> a;
		int ret2 = 0, ret5 = 0;
		for (int j = 2; j <= a; j *= 2) ret2 += a / j;
		for (int j = 5; j <= a; j *= 5) ret5 += a / j;
		cout << min(ret2, ret5) << endl;
	}
}