팩토리얼 0의 개수

Day 40: 1676 (https://www.acmicpc.net/problem/1676)

---

---

import java.math.BigInteger;
import java.util.Scanner;
 
public class b1676
{
    public static void main(String[] args)
    {
        Scanner s = new Scanner(System.in);
        int N = s.nextInt();
        
        char[] fac = getFac(N).toString().toCharArray();
        int num0 = 0;
        
        for (int i = fac.length-1; i >= 0; i--)
        {
            if (fac[i] == '0') num0++;
            else break;
        }
        
        System.out.print(num0);
    }
    
    static BigInteger getFac(int N)
    {
        BigInteger big = BigInteger.valueOf(1);
        
        for (int i = 1; i <= N; i++)
        {
            big = big.multiply(BigInteger.valueOf(i));
        }
        
        return big;
    }
}

---

피보나치(0) 호출 횟수 구하는 그런 문제 (http://puzzlers.tistory.com/entry/%ED%94%BC%EB%B3%B4%EB%82%98%EC%B9%98-%ED%95%A8%EC%88%98?category=766745) 일 것이라고 생각했는데, 생각할 것이 조금 있는 수학 문제였다. 작은 숫자의 팩토리얼이라면 그냥 계산해 구한 값을 1의 자리부터 계산하면 되겠지만, 500! 을 2초 안에 계산할 수 있을까?

할 수 있다. (????) 다만 실행시간은 순위권이 아니다. 조금 더 생각해보니, 일반 primitive 자료형들의 표현 한계와 그 한계를 위해 BigInteger를 사용해야 한다... 라는 메모리(?)에 대한 사실을 실행시간과 연관지어 기억하고 있었다.

첫번째 코드는 BigInteger을 사용하는 정말 기본적인 풀이다. 1등분의 코드를 보니 단순한 규칙이 있는 것 같았고, 확인해보니 N!은 N이 0부터 5씩 증가할 때 마다 뒤에서부터 나오는 0의 갯수가 하나씩 늘어나는 규칙을 가지고 있었다 (ex. 4! = 24, 5! = 120; 9! = 362880, 10! = 3628800). 이 싱기한 규칙을 이용해 단순하게 짠 것은 나중에 업로드.