백준 1676 (팩토리얼 0의 개수)

문제

---

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

 

 

 

 

풀이

---

문제의 N 의 범위가 ( 0 ≤ N ≤ 500 ) 이기 때문에  Integer 과 Long 의 범위를 넘어 오버플로가 발생하게 된다.

 

다른방법을 찾았다.

 

5! = 120 = 12 x 10

10! = 3628800 = 36288 x 10 x 10

15! = 1307674368000 = 1307674368 x 10 x 10 x 10

20! = 2432902008176640000 = 243290200817664 x 10 x 10 x 10 x 10

25! = 15511210043330985984000000 = 15511210043330985984 x 10 x 10 x 10 x 10 x 10 x 10

 

이렇게 나눠서 보면 10의 거듭제곱의 갯수 만큼 뒷자리에 0의 갯수가 생기게 된다는걸 알 수 있다.

10 은 2 x 5 의 형태로 나타나게 되는데 2는 짝수에 하나씩 계속 곱해지기 때문에 갯수는 부족하지 않다고 생각이 든다.

그래서 N 까지 곱을 할때 곱해지는 5의 갯수를 세야한다고 생각을 해서 5의 갯수를 세었다.

5 를 세는 방식은 N/ 5 를 하면 N 까지의 5의 배수의 개수이다.

하지만 5의 배수를 구하는게 아닌 5가 곱해진 거듭제곱의 개수를 구하는 것이기 때문에

N/5 를 한 뒤

N이 5 가 될때까지 그 수를 구해주면 된다.

 

<코드>

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

public class Main {	
	static StringBuilder sb = new StringBuilder();
	
	public static void main(String[] args) throws IOException{
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int n = Integer.parseInt(br.readLine());
		
		int count = 0;
		
		while(n >= 1) {
			count += n /5;
			n /= 5;
		}
		
		sb.append(count);
		System.out.println(sb);
	}		
}