백준 3474 //idea를 위해 table을 그려라

3474번: 교수가 된 현우 (acmicpc.net)

3474번: 교수가 된 현우

문제1 : N!완탐은 시간초과

해결 : 10!속에 2가5개, 5가7개있으면 -> 0의 개수는 둘중작은값임.(5)

10!      = 10 9 8 7 6 5 4 3 2 1

2의개수: 1     3    1     2    1

 

문제2:N이 10억이므로 N!을 1,2,3,4,...N 까지하면, 터짐

해결 : 10! 안에 2,4,8,... 의 개수를 각각세는것 만으로 가능.

구현 : 10/2 = 10!안의 2의개수 , 10/4=10!안의 4의개수, ....

10!      = 10 9 8 7 6 5 4 3 2 1

2의개수: 1     1    1     1    1

4의개수 :        1           1 

8의개수:          1

#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
int t,a;
char c;
string s;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(NULL); cout.tie(NULL);
    cin >> t;
    while (t--)
    {
        int ret2=0, ret5=0;
        cin >> a;
        for (int i = 2; i <= a; i*=2)
        {
            ret2 += a / i;
        }
        for (int i = 5; i <= a; i *= 5)
        {
            ret5 += a / i;
        }
        cout << min(ret2, ret5) << "\n";
    }
    
    return 0;
}