[Bronze V][JAVA]1676번:팩토리얼 0의 개수

[Bronze V]1676번:팩토리얼 0의 개수 - 바로가기

풀이과정

☑️팩토리얼에서 0의 개수는 5의 차수

• N의 범위는 0 <= N <= 500이다. N!을 계산하는건 비효율
• 10은 2와 5의 곱

2는 짝수이기 때문에 N!의 소인수에서 5 개수보다 적을 수가 없다. 따라서 5의 개수만 구하면 된다.

N = 10일때, 0의 개수는 2. 10! = 10(5 x 2) x 9 x 8 x 7 x 6 x 5 x 4 x ..
N = 25일때, 0의 개수는 6, 25! = 25(5 x 5) x 24 x 23 ... x 21 x 20(5 x 4) x 19 x .. x 14 x 15(5 x 3) x 13 x.. 10(5 x 2) x 9 x .. 5.. x 1

정답

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

public class Main { //유형: 수학 , 메모리제한: 128MB, 시간 제한: 2초
    static int count = 0;

    public static void main(String args[]) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());

        while (N > 0) {
            count += N / 5;
            N /= 5;
        }
        System.out.println(count);
    }
}