[BOJ_3474 | Number Theory] 교수가 된 현우

풀이

문제 자체는 크게 어려운 문제는 아니었던것 같다.

하지만, 풀이 과정에 따라서 시간 복잡도가 천차만별이 될 수 있다는 것을

3번의 실패끝에 경험했다.

몇 자리수인지를 물어보는 것이 아니라 뒷자리에 0이 몇개가 있는지를 계산하는 문제였기 때문에

비교적 간단하게 2 와 5의 개수만으로 답을 구할 수 있다.

단 이때 참고해도 될 만한 부분은

1. 2의 개수는 무조건 5의 개수보다 많으므로 굳이 2의 개수를 세느라 시간을 낭비할 필요가 없다

2. 1~N 사이의 2나 5의 배수를 탐색하는 과정에서 모든 숫자를 탐색할 필요가 없다

이 2가지 정도로 정리할 수 있겠다.

2번을 몰랐던 상황에서 1024!의 값을 구하기 위해

1~1024 까지의 모든 자연수의 2, 5의 배수개수를 세고 있었고

결과적으로 시간 복잡도가 증가하면서 시간초과에 걸리게 되었다.

해결방안으로는 for(int i=5;i<num;i*=5) 를 사용하는 것이었다.

5가 1번 들어있는 모든 수들의 개수를 더해주고

5가 한번 더 들어있는 수의 경우에는 간격을 25로 한번씩 더 더하고

5가 그 다음에도 한번 더 들어있는 수의 경우에는 125의 간격으로 한번씩 더 탐색하는 격이다.

이 방법을 사용하면

큰 수의 Factorial 값 안에 있는 5의 개수를 빠른 시간 안에 해결할 수 있다.

소스코드

import java.util.*;
 
public class BOJ_3474 {
    public static void main(String[] args){
        Scanner input = new Scanner(System.in);
        int n = input.nextInt();
        int num5 = 0;
        for(int i=0;i<n;i++){
            long num = input.nextLong();
            for(int j=5;j<=num;j*=5){
                num5 += num/j;
            }
            System.out.println(num5);
            num5 = 0;
        }
 
    }
}