[Java] 백준 풀기 1676 - 팩토리얼 0의 개수

자바 백준 1676번

실버 5

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

1676번: 팩토리얼 0의 개수

 

 

 

 

 

문제 보기

분류: 수학

 

 

 

 

 

문제 풀기

뒤에서부터 처음 0이 아닌 숫자가 나올때까지 0의 개수를 구한다. 이때, 0의 개수는 주어진 수 N에서 5의 빈도수를 세어 구한다. N보다 작은 수들 중에서 5의 배수는 1개씩, 25의 배수는 2개씩, 125의 배수는 3개씩, ... 이런 식으로 각각의 배수들을 세어서 전체 0의 개수를 구한다.

N이하의 수 중 5의 배수만 관심이 있기에 for loop는 5부터 시작하여 i *= 5 스텝으로 증가한다.

 

 

 

 

 

코드 보기

import java.util.Scanner;

public class Main {
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        int N = sc.nextInt();

        int count = countTrailingZeros(N);
        
        System.out.println(count);
    }

    private static int countTrailingZeros(int n) {
        int count = 0;
        for (int i = 5; i <= n; i *= 5) {
            count += n / i;
        }
        return count;
    }
    
}