[백준] 1676 - 팩토리얼 0의 개수 자바

문제

N!에서 뒤에서부터 처음 0이 아닌 숫자가 나올 때까지 0의 개수를 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에 N이 주어진다. (0 ≤ N ≤ 500)

 

출력

첫째 줄에 구한 0의 개수를 출력한다.

 

예제 입력

10

예제 출력

2

 

예제 입력

3

예제 출력

0

 

내 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.math.BigInteger;

public class Main_1676 {
	static int N;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		
		int cnt = 0;
		while(N >= 5) {
			cnt += N/5;
			N /= 5;
		}
		
		System.out.println(cnt);
		
		br.close();

	}
}

 

처음 문제를 접했을 때는 500!을 생각하니 BigInteger로 풀어야된다고 생각해서 해보니 메모리초과가 났다.

단순하게 생각하니까 0이 나올 때는 2와 5가 곱해지면 0이나오는데

2와 5의 쌍을 찾으려고 하면 항상 5가 2보다 적게 나오므로 5의 개수만 찾으면 된다.