3473번: 교수가 된 현우

문제

자연수 N이 주어질 때, N! (팩토리얼)의 오른쪽 끝에 있는 0의 개수를 구하는 문제입니다.

• 입력: 첫째 줄에 테스트 케이스의 개수 T가 주어지고, 다음 T개의 줄에 걸쳐 자연수 N이 주어집니다. (1 <= N <= 1,000,000,000)
• 출력: 각 N마다 N!의 오른쪽 끝에 있는 0의 개수를 줄바꿈하여 출력합니다.

링크: https://www.acmicpc.net/problem/3474

풀이: 소인수분해의 성질 활용 및 오버플로우 방지

어떤 수의 끝에 0이 붙으려면 10이 곱해져야 하고, 10은 2 * 5로 이루어져 있습니다. 즉, N!을 소인수분해했을 때 나오는 2의 개수와 5의 개수 중 짝이 맞는 개수(최솟값)가 곧 0의 개수입니다.

1. 1. 5의 개수만 구하기 (수학적 최적화): 팩토리얼은 1부터 $N$까지의 곱입니다. 이 연속된 숫자들 중 짝수(2의 배수)는 2칸마다 등장하지만, 5의 배수는 5칸마다 등장합니다. 따라서 2의 개수는 5의 개수보다 항상 많거나 같습니다. 결과적으로 2의 개수를 세어 최솟값을 비교할 필요 없이, 5가 몇 번 곱해졌는지만 세면 그것이 바로 0의 개수가 됩니다.
      • 왜 N을 5로 나눌까?: 1부터 $N$까지의 숫자 중 5의 배수는 $N / 5$개 존재합니다. 하지만 25($5^2$)의 배수는 5를 두 번, 125($5^3$)의 배수는 5를 세 번 포함합니다. 따라서 $N$을 5로 나눈 몫을 누적하고, $N$을 다시 5로 나누는 과정을 반복하면 25, 125 등의 거듭제곱 수에서 추가로 파생되는 5의 개수까지 모두 정확하게 합산할 수 있습니다.
   2. 5의 개수 합산: while문을 통해 N을 5로 나누어가며 몫을 누적합니다.

코드

import java.io.*;

public 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 t = Integer.parseInt(br.readLine());

       while (t-- > 0) {
          int n = Integer.parseInt(br.readLine());

          int cnt5 = 0;
          
          // 2의 개수는 항상 5의 개수보다 많으므로 5의 개수만 구함
          while (n >= 5) {
             cnt5 += n / 5;
             n /= 5;
          }
          
          bw.write(cnt5 + "\n");
       }

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

알고리즘 분류

수학 (Math), 정수론 (Number Theory)