[BOJ] 1676 팩토리얼 0의 개수 - JAVA

1. 문제

1676번: 팩토리얼 0의 개수

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

---

2. 풀이

뒤의 숫자가 0이 되려면 10의 배수여야 한다. 10은 2와 5의 곱으로 나오므로 2와 5가 각각 몇 번씩 나오는지 센다.

1.  i=2부터 N까지 탐색한다.

2.  현재 숫자가 2로 나누어떨어지는만큼 cnt2에 더하고, 5로 나눠떨어지는만큼 cnt5에 더한다.

3.  마지막에 cnt2와 cnt5의 최솟값을 출력한다. 짝이 맞아야 10이 나오기 때문이다.

import java.io.*;

public class BOJ_1676_팩토리얼0의개수 {
   public static void main(String[] args) throws IOException {
      int N = Integer.parseInt(new BufferedReader(new InputStreamReader(System.in)).readLine());

      int cnt2 = 0;
      int cnt5 = 0;

      int num;
      for(int i=2;i<=N;i++){
         num = i;
         while(num%2==0){
            cnt2++;
            num/=2;
         }
         while(num%5==0){
            cnt5++;
            num/=5;
         }
      }

      System.out.println(Math.min(cnt2,cnt5));
   }
}

---

3. 결과