백준 1676 ( Java ) - 팩토리얼 0의 개수

팩토리얼 0의 개수

 

문제 풀이

처음 떠오르는 풀이법은 N!을 직접 구해서 뒤에서부터 0이 아닌 숫자가 나올때까지 0의 개수를 구하는 방법이지만 

N 이 조금만 커져도 시간 제한에 걸리게된다. 그러므로 다른 풀이법을 생각해야한다.

 

팩토리얼 숫자에서 0이 증가하는 경우를 생각해보자. 2 * 5 가 포함된만큼 0이 증가하는것을 알 수 있다.

어느 경우에서든 2보다 5가 더 많으므로 n 이하의 숫자들중에서 5 , 25 ,125가 포함된 갯수들을 구하면된다.

n <= 500 이므로 125 까지만 찾으면된다.

 

import java.util.Scanner;
 
public class Main {
  public static void main(String []args) {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    int count = 0;
    while (n >= 5) {
      count += n / 5;
      n /= 5;
    }
    System.out.println(count);
  }
}