ETC. 백준 알고리즘 자바 1676 ‘팩토리얼 0의 개수’ 문제풀이

Problem

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

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

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

Solution

이 분의 도움을 받았다.
https://ksj14.tistory.com/entry/BackJoon1676-%ED%8C%A9%ED%86%A0%EB%A6%AC%EC%96%BC-0%EC%9D%98-%EA%B0%9C%EC%88%98
처음에 15! 까지 일일이 구해 본 결과 5, 10, 15 순으로 0의 개수가 1, 2, 3으로 증가한다는 것을 알 수 있었다. 그래서 바로 입력 받은 값이 5의 배수이면 5로 나눈 몫이 정답이라고 풀었으나 오답이었다. 위에 블로거분과 같이 25!의 경우 25는 5의 제곱이므로 0의 개수가 원래 나와야 하는 5개보다 1 더 많이 나온다. 따라서 그 부분들에 대한 처리를 위에 블로그와 같이 하면 된다.

Code

import java.util.Scanner;
public class Main {
	public static void main(String[] args) {
		int n = new Scanner(System.in).nextInt();
		
		int cnt2 = 0, cnt5 = 0;
		for(int i = 2; i <= n; i *= 2) cnt2 += n/i;
		for(int i = 5; i <= n; i *= 5) cnt5 += n/i;

		System.out.print(Math.min(cnt2, cnt5));
	}
}