[Algorithm/Java][백준] 1676번 팩토리얼 0의 개수

[백준] 1676번 팩토리얼 0의 개수

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

문제접근

처음에는 그냥 팩토리얼 재귀 함수를 이용해서 단순하게 0의 개수를 셀려고 했다. 근데 입력의 범위가 500까지 였고 500!는 long으로도 커버가 되지 않는 범위였다. 그래서 검색을 해본 결과!@! 맨 뒤에서 연속되는 0의 개수를 센다는 것은 2 * 5 의 갯수가 몇개가 있는지와 같다!!라는 엄청난 사실을 알게 되어서 이를 코드로 구현하였다....대박...

Code

import java.util.Scanner;

public class BOJ1676 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int num = sc.nextInt();
        int twoCnt = 0;
        int fiveCnt = 0;
        for(int i = 2; i<=num; i++){
            int n = i;
            while(n % 2 == 0){
               twoCnt++;
               n /= 2;
            }
            while(n % 5 == 0){
                fiveCnt++;
                n /= 5;
            }
        }
        int cnt = Math.min(twoCnt,fiveCnt);
        System.out.println(cnt);
    }
}

어려웠던 점 / 배운 점 / 느낀 점

500!이 엄청난 수였다는것을 3번이나 틀렸을 때 깨달았다... 2 * 5의 갯수일 줄은 생각도 못했는데 이걸 혼자서 생각해낸 사람들은 정말 대단한다........