[백준/Java] 1676 팩토리얼 0의 개수*

문제

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

# 입력

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

# 출력

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

 

 

 

---

 

 

 

처음 문제를 마주했을 때는 입력 값에 대한 팩토리얼 값을 구하고, 뒤의 0의 개수를 구해나가고자 했다.

하지만 이 방법으로 문제를 풀었을 때 계속해서 "시간 초과" 가 발생했다.

 

직접 팩토리얼을 구해내는 것보다 훨씬 좋은 방법이 있었다 . .우선 실제 팩토리얼 값을 보면 다음과 같다.

 

 

자세히 살펴보면 5의 배수마다 0의 카운트 값이 증가하는 것을 볼 수 있다.

여기서 중요한 점은, 입력 값이 25일 때는 카운트 값이 1이 아닌 2가 증가한다는 것이다.

 

뒷자리에 0이 N개 있다는 의미는 2와 5가 N개씩 짝지어 존재한다는 것이다.

팩토리얼 값을 보면 2는 5보다 작은 수여서 연속된 수를 곱하게 되면 자연스레 모든 값들의 소인수분해들은2의 개수가 5의 개수보다 많다.

 

즉, 기본적으로 5의 개수에 따라 값이 변화한다고 보면 된다.

그리고 5의 N승에 따라 카운트 값을 하나 더 추가해주면 된다 !

⇒ 단순히 5로 나눌 것이 아니라 반복문을 통해 5로 나누며 누적합을 해주어야 한다.

 

 

풀이

import java.io.*;

public class Main {
	public static int countZero(int n) {
		int cnt = 0;

		while(n >= 5) {
			cnt += n / 5;
			n /= 5;
		}

        return cnt;
	}

    public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		System.out.println(countZero(Integer.parseInt(br.readLine())));
	}
}

 

 

© 참고

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

https://st-lab.tistory.com/165

1676번: 팩토리얼 0의 개수