[알고리즘] 백준 3474

백준 3474번 교수가 된 현우

해결 과정 요약

0의 개수를 구하는 것을 2 x 5 쌍의 개수를 세는 것과 같다.
바로 먼저 떠오른 방법은 1부터 1씩 더해가면서 2와 5로 나누어떨어지면 2와 5의 개수를 늘려주는 방식이다.
하지만 입력의 최댓값을 보면 10억이다. 보통 1억에 1초정도 걸린다고 예상하므로 위 방법은 매우 비효율적이다.
그래서 다시 생각해보았다. 2보다는 5의 개수가 훨씬 적으니 5의 갯수만 세어도 된다는 것을 알았다.
5의 개수를 세기위한 방법은 두가지가 떠올랐다.
하나는 그냥 5씩 더해가면서 5로 나누어떨어지는 횟수를 모두 더하는 방법.
하지만 이 방법 또한 2억번의 탐색을 해야하므로 시간초과가 날 가능성이 매우 높다.
두번째 방법은 5로 나누어 떨어지는 갯수 +
5 x 5 로 나누어 떨어지는 갯수 +
5 x 5 x 5 로 나누어 떨어지는 갯수 ...
이 방법을 코드로 적으면 다음과 같다.

int ret=0;
for(int i=5; i<=num; i*=5){
    ret += num/i;
}

풀이

#include <bits/stdc++.h>
using namespace std;

int N,num;

int countZero(int num){
    int ret=0;
    for(int i=5; i<=num; i*=5){
        ret += num/i;
    }
    return ret;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> N;
    for(int i=0; i<N; i++){
        cin >> num;
        cout << countZero(num) << "\n";
    }
    return 0;
}

코멘트

시간복잡도에 대해서 알고있냐고 묻는듯한 문제.
입력값의 최대치를 보고 어떻게 하면 시간을 더 줄일 수 있을지 고민하면서 풀었다.