1676.팩토리얼0의개수

문제

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

입력

첫째 줄에 N이 주어진다. (0 ≤ N ≤ 500)

출력

첫째 줄에 구한 0의 개수를 출력한다.

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
2 초	128 MB	70550	33569	28012	47.323%

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

풀이

알고리즘

이문제는 입력값을 잘 살펴야한다. (0 ≤ N ≤ 500)의 범위로 500! 이라면 아래와 같은 값이 나온다.

1220136825991110068701238785423046926253574342803192842192413588385845373153881997605496447502203281863013616477148203584163378722078177200480785205159329285477907571939330603772960859086270429174547882424912726344305670173270769461062802310452644218878789465754777149863494367781037644274033827365397471386477878495438489595537537990423241061271326984327745715546309977202781014561081188373709531016356324432987029563896628911658974769572087926928871281780070265174507768410719624390394322536422605234945850129918571501248706961568141625359056693423813008856249246891564126775654481886506593847951775360894005745238940335798476363944905313062323749066445048824665075946735862074637925184200459369692981022263971952597190945217823331756934581508552332820762820023402626907898342451712006207714640979456116127629145951237229913340169552363850942885592018727433795173014586357570828355780158735432768888680120399882384702151467605445407663535984174430480128938313896881639487469658817504506926365338175055478128640000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

굉장히 큰수이기때문에 Long의 범위도 넘어가게 되고, BigInteger를 사용해서 구해야한다. 이것보다 쉽게 풀수있는 방법을 알아보자.

일단 뒷자리가 0이 나오는 경우는 언제인지 생각해보면, 2와 5가 곱해질때다. 즉, 소인수분해를 해서 2와 5가 존재할경우 뒷자리는 0으로 끝난다.

• 5! - 120 (1)
• 10! - 3628800 (2)
• 15! - 1307674368000 (3)
• 20! - 2432902008176640000 (4)
• 25! - 15511210043330985985984000000 (6)

그리고 입력값이 25일때는 카운트가 2 증가한다.

뒷자리에 0이 n개 있다는 의미는 2와 5가 n개씩 짝지어 존재한다는 듯이다. 팩토리얼 값에서 2는 5보다 작은수여서 연속된 수를 곱하게 되면 자연스럽게 모든 값들의 소인수 분해들은 2의 개수가 5의 개수보다 많다.

다시말해 5의 개수에 따라 값이 변화한다. 5의 n승에 따라 카운트값을 하나 추가해주면 된다. 즉, 단순히 5로 나눌것이 아니라 반복문을 통해 5로 나누면서 누적합을 구해준다.

이를 작성한 코드는 두번째시도를 참고하자.

코드

첫번째시도

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

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

        int n = Integer.parseInt(br.readLine());  
        char[] arr = (String.valueOf(factorial(n))).toCharArray();  
        int count = 0;  

        for(int i=arr.length-1; i>=0; i--){  
            if(arr[i] == '0'){  
                count++;  
            }else{  
                System.out.println(count);  
                break;  
            }  
        }  
        br.close();  
    }  

    public static BigInteger factorial(int n){  

        //biginteger로 사용해야한다.  
        BigInteger result = new BigInteger(String.valueOf(1)); 

        for(int i=2; i<=n; i++){  

            //범위가 500까지 이므로 500!은 Long의 범위도 넘어간다.  
            result = result.multiply(BigInteger.valueOf(i)); 
        }  

        return result;  
    }  
}

문제를 처음 접했을때 생각난 방법은 다음과같다.

1. 팩토리얼을 돌린 값을 구한다.
2. 뒤에서 부터 0의 개수를 세서 출력한다.

하지만...실패...

문제는 위의 알고리즘흐름에 적어놓았듯 500!까지의 범위에서 Long을 넘어가게 된다. 그래서 BigInteger로 작성하니 정상적으로 작동하였다.

두번째 시도

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

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int num = Integer.parseInt(br.readLine());
        int count = 0;

        while (num >= 5) {
            count += num / 5;
            num /= 5;
        }
        System.out.println(count);
    }

}

성공!!