[P&B] #83 BAEKJOON 1676

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

문제 설명

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

 

입력

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

 

출력

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

 

나의 문제 풀이 코드

import java.io.*;
public class bj1676 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int N = Integer.parseInt(br.readLine());
        int count = 0;

        while (N >= 5) {
            count += N / 5;
            N /= 5;
        }
        bw.write(String.valueOf(count));
        bw.flush();
    }
}

 

문제 풀이 코멘트

이 문제를 팩토리얼을 모두 계산하여 셀수 있다면 편하겠지만 500의 경우 500!는 엄청나게 큰 수가 나옵니다.

그렇다면 다르게 생각해보아야 합니다. 뒷자리가 0이 나오는 경우는 2와 5가 곱해져 있을 때 입니다. 

이 말은 즉, 소인수분해를 해서 2와 5가 존재할 경우 뒷자리는 0으로 끝난다는 것입니다.

실제 팩토리얼 값을 나열해보면 다음과 같습니다.

처음에는 숫자에서 5를 나눈 몫만큼 0이 존재하는 것 처럼 보이지만 25부터는 카운트 값이 2가 증가합니다.

 

뒷자리가 0이 n개 있다는 의미는 2와 5가 n개씩 짝지어 존재한다는 의미입니다. 하지만 일반적으로 소인수 분해들의 2의 개수가 5의 개수보다 많습니다. 즉, 기본적으로 5의 개수에 따라 값이 변화하므로 5의 n승에 따라 카운트 값을 한개 더 추가하면 됩니다.

한마디로 단순히 5로 나눌 것이 아니라 반복문을 통해 5로 나누면서 누적합을 해주어야 합니다.

그럼 위의 코드와 같이 while문이 구현됩니다.