백준 - 1676번 - 팩토리얼 0의 개수

1676번

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

public class Main {

	public static void main(String[] args) throws IOException {

		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		int num = Integer.parseInt(bf.readLine());

		int cnt = 0;
		while (num >= 5) {
			cnt += num / 5;
			num /=5;
		}

		System.out.println(cnt);
	}
}

풀이

---

입력받은수 팩토리얼을 구했을때 1의자리부터 0이 몇개가 연속되는지 출력하는 문제다.

이 문제를 진짜 팩토리얼을 구해서 0의 갯수를 카운트할 수는 없다. 수의 범위가 어마어마하게 필요하기 때문이다.

수학적인 접근이 필요한데, 0인 생기는 경우는 2와 5를 곱했을때다. 그래서 최소공배수에 2와 5가 있을때마다 0이 생기는 규칙을 이용해야한다. 그런데 2는 어차피 5보다 많이 들어가므로 5가 몇번 제곱되는지만 생각하면된다.

결과는 위와 같이 매우 간단한 로직으로 풀린다...