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

 

생각의 방향

처음 문제를 봤을 때 부터 이해를 못했다. 처음 0이 아닌 숫자.... 뭐요...? 

이게 뭘 의미하는거지...10! 이라고 했을 때, 10x9x8x7x6x5x4x3x2x1 .. 0이 도대체 어딨지?_? 라는 생각 뿐. 알고리즘 기초 1/2 강의에서 <수학> 파트 쪽에 수록된 이 문제를 이해하는 것 조차 쉽지 않아, 결국 구글링의 힘을 빌렸다. 

 

구글링 결과

역시 검색 찬스! 팩토리얼의 결과값을 보니, 문제에서 말하는 '팩토리얼 0의 개수'가 결과값에 있는 '0' 의 개수를 의미하는 것이구나... 팩토리얼 결과값에서 0이 나오려면, 2x5 가 무조건 곱해져 있어야했다. 

 

 

2x5 이 쌍으로 있는 경우, 팩토리얼 결과값에 0의 개수도 차곡차곡 쌓인다. 결과값을 소인수분해 해보면 2와 5가 존재하는 것을 볼 수 있다! 0이 n개 있다는 것은 2와 5가 n개씩 쌍으로 있다는 의미였다. 

🔥 2와 5가 몇 쌍인지 = 0이 몇 개인지 파악하는 것이다.

그런데 주의할 것이 있다. 25~29 팩토리얼 구간을 보면 0의 개수가 +1이 아닌 +2로 늘어났다. 소인수분해를 해보면, 5의 개수를 기준으로 0의 개수가 늘어난 것을 확인할 수 있다. 2는 5보다 작은 수라서 5보다 개수가 월등히 많지만 2의 개수만큼 0의 개수가 늘어나진 않았다. 즉 5가 팩토리얼 결과값에서 0의 개수를 결정하는 요소임을 알 수 있다.  

 

 

package quiz;

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

/**
 * N!에서 뒤에서부터 처음 0이 아닌 숫자가 나올 때까지 0의 개수를 구하는 프로그램을 작성하시오.
 *
 * 첫째 줄에 구한 0의 개수를 출력한다.
 *
 * 뒷자리에 0이 나오는 경우는 2와 5가 곱해진 때, 즉, 10이 곱해진 경우이다.
 * 소인수분해를 해보면, 2와 5가 존재하는 경우 뒷자리가 0으로 끝난다.
 *
 * 뒷자리에 0이 n개 있는 것은, 2와 5가 n개씩 짝지어 존재한다는 의미다.
 * 팩토리얼에서 25~30 팩토리얼은 0의 개수가 5의 개수만큼 증가함을 알 수 있다.
 * 즉, 5의 배수마다 팩토리얼이 증가한다고 보면 되어 문제에서 5의 배수를 고려한다.
 *
 *
 */
public class _1676 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());

        //뒷자리에 0이 나오는 경우- 2 와 5가 곱해졌을 때.
        //=소인수분해해서 2와 5개 존재할 경우 뒷자리는 0으로 끝남을 알 수 있다.

        int count =0;
        while(n>=5){
            count+= n/5;
            n /= 5;
        }

        System.out.println(count);


    }
}