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

 

 

1676번: 팩토리얼 0의 개수

 

문제 이해 & 기본 개념

• 팩토리얼의 결과 값에서 끝에 0의 개수를 구하는 문제
• N이 최대 500까지 들어오므로 팩토리얼을 직접 계산하는 방법은 불가
  • BigInteger를 사용하면 가능하긴 하겠지만, 좋은 방법은 아닌 듯함

---

중요 포인트

• 팩토리얼을 계산하지 않고 0의 개수를 알아내는 방법을 찾는게 중요
• 어떤 경우에 끝에 0이 붙는지를 생각해보면 쉽게 규칙을 찾을 수 있다.

---

최종 풀이

• 끝자리에 0이 붙는 경우는 10(2 x 5)을 만났을 때이다.
• 2와 5가 곱해지는 순간 10이 되어 끝자리에 0이 생기게 된다.
• 즉, 2x5가 몇 번 나오는지만 알면 0이 몇 개 붙는지 알 수 있다.
• 2와 5가 짝을 이루어야 하며, 둘 중 하나만 혼자 곱해지는 건 의미가 없다.
• 2와 5중에 더 적게 등장하는 값을 찾아야하는데, 2는 모든 짝수의 약수이므로 5보다 많이 등장할 수 밖에 없다.

 

=> n!에서 n에 5가 몇 번 들어가는지만 찾으면 된다.

---

소스 코드

public class Main {
 
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
 
		int n = in.nextInt();
		int count = 0;
 		/* 5가 하나 지워진다는 뜻은 한 번 등장한 5가 지워진다는 뜻 */
		while (n >= 5) {
			count += n / 5; // n을 5로 나눌 때마다 5가 하나씩 사라짐
			n /= 5;         // 5를 하나 지웠으므로, n을 5로 나눈 뒤 반복
		}
		System.out.println(count);
	}
}