[java 백준] 실버 4/ 1676번 팩토리얼 0의 개수

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

1676번: 팩토리얼 0의 개수

---

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
    public static int n;
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
 
        n = Integer.parseInt(st.nextToken());
        int total = 1;
 
        int cnt = 0;
 
        while (n >= 5) {
            cnt += n / 5;
            n /= 5;
        }
 
        System.out.println(cnt);
 
    }
 
}

 

---

문제의 핵심은 뒤에서부터 처음 0이 아닌 수가 나올때 까지 0의 개수이다.

그렇다면 0이 되려면 2와 5가 필요하다는 것(2*5=10)을 생각해볼 수 있다.

그런데 어차피 팩토리얼이므로 5가 나온 뒤 2가 나올거고, 당연히 2가 5의 개수보다 많을거기에 5의 개수가 0의 개수랑 같다고 생각해 볼 수 있다.

그러면 소인수분해를 통해 이 문제를 해결해볼 수 있는데, 

예를 들어 5!이면 120이다. 이것을 소인수 분해하면 2^3*3*5가 된다 여기서 5의 개수는 1이고, 0의 개수도 1이다. 

10! 의 경우 0의 개수가 2인데 10! 안에는 5가 2번 들어가 있다. 

20!의 경우 0의 개수가 4인데 여기 안에도 5,10,15,20으로 5가 4번 들어가 있다.


그렇다면 n에서 5를 나누면 되지 않을까? 하는 생각이 든다. 하지만 지금까지는 5*1, 5*2, 5*3, 5*4 등 5가 1제곱만 포함되지만, 

50!의 경우 25나 50이 포함되면서 5의 2제곱이 포함된다. 이런경우 5의 개수를 유실할 수 있다. 

그러므로 n을 5로  나눠줌으로 써, 여러번 5가 곱해진 경우도 포함시켜준다.  

더이상 n이 5로 나눠질 수 없을 때 까지 반복문을 돌려준다. (n이 5보다 크거나 같을 때까지만) -->while문 사용 



while(n>=5){

  cnt+=n/5; // 5가 1제곱만 포함된 경우

  n/=5; // 5가 n 제곱 ( 단, n>1) 포함된 경우를 찾기 위해 5로 한번더 나눠준다.

 

추가

---

10을 만들려면 2와 5가 필요하다. 그렇기에 2와 5를 각각 나눈것을 고려해볼것이다. 즉,2의 승수와 5의 승수 중 더 작은 값을 가져오는 알고리즘을 구현해볼 것이다. 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
    public static int n;
 
    public static int count2(int n) {
        int cnt = 0;
        while (n >= 2) {
            cnt += n / 2;
            n /= 2;
        }
        return cnt;
    }
 
    public static int count5(int n) {
        int cnt = 0;
 
        while (n >= 5) {
            cnt += n / 5;
            n /= 5;
        }
        return cnt;
    }
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
 
        n = Integer.parseInt(st.nextToken());
        System.out.println(Math.min(count2(n), count5(n)));
 
    }
 
}