[BOJ] 1676 - 팩토리얼 0의 개수 JAVA

www.acmicpc.net/problem/1676

1676번: 팩토리얼 0의 개수

문제

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

입력

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

출력

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

예제 입력 1 복사

10

예제 출력 1 복사

2

예제 입력 2 복사

3

예제 출력 2 복사

0

 

 

 

 

 

풀이 .

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());

        int cntOfFive = 0;
        cntOfFive += n / 5;
        cntOfFive += n / 25;
        cntOfFive += n / 125;

        System.out.println(cntOfFive);
    }
}

 

n을 소인수분해 했을 때 10이 즉, 뒤에 0이 붙을 수 있는 경우는 (2 * 5) 쌍이 나올 때 뿐이다.

즉, n을 소인수분해 하여 (2*5) 꼴이 몇 개 나오는지를 알아내면 된다.

 

그런데 2는 짝수가 나올 때마다 하나씩 추가되기 때문에 무조건 5보다 많이 나올 수밖에 없다.

따라서 n 안에 5의 배수가 몇 번이나 들어있는지를 구하면 그게 곧 (2 * 5) 쌍의 개수이다.

 

여기서 주의할 점은, 25, 125 등의 수는 5의 배수가 맞긴 하지만 5가 하나만 들어있는 게 아니다

(25 = 5 * 5, 125 = 5 * 5 * 5 ... )

 

즉, 5의 배수의 개수를 구한 다음 25의 배수의 개수를 구해서 25 = 5 * 5 에서 남아있는 5를 한 번 더 세어줘야 한다.

(125는 5 * 5* 5 이므로 5가 한 번 더 들어가니깍 125의 배수의 개수도 구해야 한다.)

 

n의 제한범위 500 안에서 5의 지수승 꼴은 최대 5^3 = 125 까지만 등장하기 때문에 125의 배수의 개수까지만 구해주면 된다.