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

문제

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 fac = 1;
        for (int i = 1; i <= n; i++) {
            fac *= i;
        }

        String[] str = String.valueOf(fac).split("");

        int count = 0;
        for (int i = str.length-1; i > 0; i--) {
            if (!str[i].equals("0")) break;
            count++;
        }

        System.out.println(count);
    }
}

 

처음 풀었을 때 단순하게 팩토리얼 값을 계산해서 문자열 배열로 자른 후에 뒤에서부터 0이 아닌 수가 나올 때까지 count를 세서 출력하였다. 이랬더니 바로 틀렸다고한다..

 

⭕ 정답 코드

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 count = 0;
        while(n>=5){
            count+=(n/=5);
        }
        System.out.println(count);
    }
}

 

구글링을 해보니 이 문제는 팩토리얼이 만들어지는 과정을 잘 생각해봐야 했다.

0이 만들어지려면 10이라는 수가 만들어져야하고, 10의 인수는 2와 5이다. 그런데 2는 항상 5보다 많이 생성되기 때문에 5는 항상 2를 짝으로 가지게 된다. 2와 5가 짝이 될 때마다 10이 만들어지고 0의 갯수가 늘어나게 되는 것이다. 그렇기 때문에 결론적으로 5로 나누어지는 횟수를 알면 되는 문제였다.

n	5가 곱해진 개수
0~4	0
5~9	1
10~14	2
...	...
n*5 ~ (n+1)*5-1	n

 

제출 현황