1676 팩토리얼 0의 개수 JAVA

 

 

 

https://www.acmicpc.net/problem/1676

이번 문제는 N!이 뒤에 몇개의 0이 있는지 구하면 된다.

우선 0을 만들기 위해선 당연히 2와 5의 곱으로 이루어져야 한다.

이외의 경우엔 절대 없다.

따라서 이 문제를 해결하기 위해선, 2와 5의 지수를 구하고, 더 작은 값이 0의 개수가 될 것이다.

 

그럼 어떻게 소인수분해를 하는 것이 좋을까?

팩토리얼을 진짜 계산해버리는거? 나눗셈? 

 

우선 10! 팩토리얼도 내가 알기로 300만? 정도 되는걸로 알고 있다. 이건 너무 아닌거 같은 방법이다.

 

나는 이렇게 소인수 분해를 하였다.

 

예를 들어, 30까지의 수가 있을 때 5의 지수의 개수는 다음과 같이 구할 수 있다.

1. 5의 배수의 개수를 구한다. (파란색)    : 6개

2. 5^2의 배수의 개수를 구한다(주황색) : 1개

 

1	2	3	4	5	6	7	8	9	10
11	12	13	14	15	16	17	18	19	20
21	22	23	24	25	26	27	28	29	30

 

total : 6 + 1 = 7 

 

쉽게 이해했을 것이다.

 

import java.io.*;
public class M1676 {
    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;

        while(N > 0)
            cnt += N /= 5;

        bw.write(String.valueOf(cnt));
        bw.flush();
    }
}

 

 

나는 이런 문제의 경우에, Scanner와 BufferedReader간의 시간 차이가 적을줄 알았지만, 아래와 같이 시간차이가 은근히 있었다.

근데 이외로 시간 차이가 별로 안났고, 메모리도 별 차이가 없었다..

뭐지..? 하지만 확실한 건, 정수의 범위가 크면 클수록 2번째의 효율이 더 좋아질 것이라는 거다.