[cpp 알고리즘] 백준 3474 교수가 된 현우

[백준] 3474 교수가 된 현우 cpp(c++) 풀이

알고리즘: 수학, 정수론

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

문제 요약

- 자연수 N이 주어지면 N!의 오른쪽 끝에 있는 0의 개수를 구하기

풀이 정리

-  2의배수*5의배수로 0이 생기는데, 2의 배수는 많기 때문에 5의 배수의 최대 개수를 구하면 된다. 

ex) 60!의 경우는 5의 배수(60/5 =12)와 25의 배수(60/25=2)의 개수를 합친 12+2=14 로 답이 14가 나온다.

C++ 코드

#include <iostream>
#define ll long long
using namespace std;

ll T, N;
int main(){
    
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    cin >> T;
    while(T--){
        cin >> N;
        
        ll temp = 5;
        ll ans = 0;
        while(temp <= N){
            ans += (N/temp);
            temp *= 5;
        }
        cout << ans << "\n";
    }
    
    return 0;
}

25%에서 시간초과

ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);

 

- 처음에 시간초과가 발생했다.

- 하지만 더 줄이는 방법을 모르겠어서, 입/출력 시 시간을 단축시켜주는 위 코드를 넣으니까 해결되었다. 

- 테스트케이스로 입출력을 자주 받는 경우에는 이 코드를 꼭 잊지 말아야겠다!