[문제 풀이] 백준 1676번 팩토리얼 0의 개수 JAVA

백준 1676번 문제는 N이라는 숫자를 입력받아 N! 에서 뒤에서부터 처음 0이 아닌 숫자가 나올 때까지

0의 개수를 구하는 프로그램을 작성하는 문제이다.

예를 들어 N=10일 경우 N!=3628800 정답은 2가 되게 된다. 

 

문제를 읽고 처음에는 N!을 계산 후 10으로 나누어서 몇 번 만에 나머지가 생길까를 측정하고자 했지만 N의 범위는 1부터 500으로 500! 의 경우 말도 안 되게 큰 수가 나오는 것을 확인했다.  본 문제의 시간제한이 2초이므로 500! 을 구하고 10으로 나누어서 0의 개수를 구하는 것은 불가능했다.

 

그래서 1부터 차례로 팩토리얼 값을 구하다 보니 반복되는 패턴이 있었는데 바로 5의 배수일 때마다 0의 개수가 증가하는 패턴을 가지고 있다는 규칙을 찾았다. 하지만 1개씩 증가하는 것이 아니라 불규칙하게 증가하고 있었다.

예를 들어 5에서 0의 개수가 1개 10에서 2개 20에서 4개 이면 25에서는 5개라고 생각하지만 6개였다.

5의 배수마다 증가하니까 n/5를하고 n=n/5를 넣어준 후 이를 n이 5보다 작을 때까지 반복하면 5의 개수를 정확하게 측정이 가능할 것 같아서 식으로 만들어 풀어본 게 아래의 코드이다. 

import java.util.Scanner;
public class Main{
    public static void main(String args[]){ 
        Scanner s=new Scanner(System.in);
        int n=s.nextInt();
        int cnt=0;
            while(true){
                if(n/5>0){cnt+=n/5;n/=5;}
                else{break;}
            }
            System.out.print(cnt);

        
    }
}

 

해당 문제는 규칙은 빠르게 찾았지만 계산하는 시간과 또 다른 규칙을 찾는데 많은 시간을 소비했다. 

그리고 약간의 운도 따른것같다. 그래서 다른 사람들이 어떻게 풀었는지 아래에서 분석해보고자 한다.

 

분석해 본 결과 핵심개념은 본인이 소개한 것도 비슷한 것 같지만 조금은 다른 것 같아 다시 정리해보고자 한다.

먼저 5의 배수일때마다라고 했는데 사실은 뒤에 붙은 0의 개수는 곱해진 10의 개수를 세는 것과 동일한 것이라

10= 2 * 5 2와5가 같이 나오는 것을 세야 하는데 2는 짝수가 많아 충분하고 5의 개수만 세면 된다.

즉 N!에서 5가 몇 번 곱해지는지를 구하면 0의 개수를 알 수 있다는 것.

그래서 25 같은 경우 5로 나누면 5개이지만 25=5*5라서 5가 하나 더 있는 것이다 25는 5개 아닌 6개인 것이 확인 가능하다.