200928 월 [BOJ] 1676

BOJ 1676

factorial 값을 구하는 재귀함수를 사용했더니 시간초과😬

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main {	

	
    public static void main(String[] args) throws IOException {
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    	
    	int N = Integer.parseInt(br.readLine());
    	
    	int cnt = 0;
    	for(int i=1;i<=N;i++) {
    		int tmp = i;
    		while(tmp % 5 == 0) {
    			tmp /= 5;
    			cnt++;
    		}
    	}
    	
    	bw.write(String.valueOf(cnt));
    	
       	bw.flush();    	
    	bw.close();
    }
}

다른 사람들 풀이를 참조했다.
팩토리얼 값 끝에 0이 붙으려면 10이 곱해져야 한다.
즉, 10의 약수인 2와 5가 한번씩 나올 때에 0이 붙게된다는 말인데,
2는 어차피 많은 수들의 약수이기 때문에 그 수가 많을 거고, 결국 5의 갯수에 값이 달려있는 셈이 된다.