[백준] 1676번 : 팩토리얼0의개수 - 자바(JAVA)

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

1676번: 팩토리얼 0의 개수

 

문제 해석

N!이 값이 가지는 0의 개수를 구해야 합니다.

만약 N!이 값이 1234000이라고 가정하면 0의 개수는 3개입니다.

 

문제 풀이 전 설계

1234000을 분리하면 1234 * 1000 으로 분리할 수 있습니다.

이것 또 분리하면 1234 * 10 * 10 * 10 으로 분리할 수 있습니다.

즉, 0의 개수는 10의 개수와 동일합니다.

 

또한 10은 2 * 5입니다.

 

결국 우리는 N!의 수가 2^x * 5^y 가 몇 개 나오는지 찾고 Math.min(x, y)를 하면 정답이 나오게 됩니다.

 

코드

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

        int twoCount = 0;
        int fiveCount = 0;
        int cur = 0;
        for(int i=N; i>=1;i--){
            cur = i;
            while(cur%2 == 0){
                cur = cur/2;
                twoCount++;
            }
            while(cur%5 == 0){
                cur = cur/5;
                fiveCount++;
            }
        }
        int result = Math.min(twoCount,fiveCount);
        System.out.println(result);

    }
}