[백준] 1676 - 팩토리얼 0의 개수 (자바/Java)

문제

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

입력

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

출력

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

---

0의 개수는 2*5가 몇 개 있는지를 확인하면 된다.

N의 팩토리얼은 1*2*...*(N-1)*N 까지니까 2부터 N까지 for문을 돌며 2와 5를 소인수로 갖는 i에 대해 2와 5의 수를 세서 cnt변수에 더하였다.

2*5의 짝이 맞아야 0이 생기기 때문에 2와 5의 개수 중 작은 수를 출력하였다.

 

tmp에 i를 넣지 않으면 2와 5의 배수를 구하는 과정에서 i가 변화하여 for문이 무한루프에 빠진다. tmp에 i를 넣어서 for문에 영향을 주지 않도록 해야 한다.

package Silver.s5;

import java.util.Scanner;

public class BOJ_1676_팩토리얼0의개수 {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();

		int cnt2 = 0;
		int cnt5 = 0;
		for (int i = 2; i <= N; i++) {
			// 2의 개수
			int tmp = i;
			while (tmp % 2 == 0) {
				cnt2++;
				tmp /= 2;
			}

			// 5의 개수
			while (tmp % 5 == 0) {
				cnt5++;
				tmp /= 5;
			}

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

}