[Java] 백준(실버-5) 1676번 - 팩토리얼 0의 개수

문제 풀이

---

이번 문제는 단순한 구현 문제이다.

아이디어 도출

이 문제는 단순히 N!의 값을 팩토리얼 연산을 통해 구해서 0을 구할 수 있지만, 입력값의 범위를 생각하면 출제자의 의도는 다른 것이라는 것을 알 수 있다.

최대 500! 까지의 값을 구해야 하는데 BigInteger 클래스를 사용해야만 500! 까지의 값을 구할 수 있다.

물론, BigInteger 클래스를 사용하여 팩토리얼 연산 후 0의 개수를 셀 수도 있겠지만, 여기서는 출제자가 의도한 0의 개수를 세는 것은 다른 방법을 이용하려고 한다.

N!의 값에서 뒷자리가 0이 나오는 경우를 잘 생각해보면 10으로 나누어 떨어질 때를 생각해볼 수 있다. 이 말은, 소인수분해를 해서 2와 5가 존재할 경우 뒷자리는 0으로 끝난다고 볼 수 있다.

예시를 한번 들어보자.

30 = 2*3*5
231400 = 23*52*13*89

30과 231400 모두 2와 5가 포함된다. 즉, 소인수분해의 성질을 이용해야 한다는 것이다.

소인수분해의 성질을 통해 살펴보면, 뒷자리가 0이 N개 있다는 것은 2와 5개 N개씩 쌍으로 존재한다는 것을 알 수 있다.

30과 231400이라는 수도 소인수분해값을 보면 30은 2와 5가 1개씩 쌍으로 1개가 있으며, 231400은 2는 3개, 5는 2개가 있어 쌍으로 2ㅐ가 있다. 30의 0의 개수는 1개, 231400의 0의 개수는 2개라고 보면 된다.

그런데, N!의 값을 보면 2는 5보다 작기 때문에 소인수분해시, 2의 개수는 5의 개수보다 많게 된다. 그래서 5의 개수에 초점을 두어야 한다.

문제 풀이를 위한 생각한 아이디어는 다음과 같다.

• N을 5로 나눠가면서 5로 나눌때마다 카운트를 세면 된다.

  N을 5를 나눠가며 갱신할 때마다 카운트를 하는 것이 0의 개수를 세는 것과 같다.

문제 풀이를 위해 작성한 코드는 아래와 같다.

작성코드

---

import java.io.*;

class Main {    

    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 result = 0;
        
        while(N >= 5) {
            N /= 5;
            result += N;
        }

        bw.write(result+"\n");

        bw.close();
        br.close();
    }    

}

출처

---

• 해당 문제의 저작권은 문제를 만든이에게 있으며 자세한 내용은 문제 링크에서 참조바랍니다.