백준 9461문제 (실버 5)

url: 1676번: 팩토리얼 0의 개수 (acmicpc.net)

 

 

문제

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

입력

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

출력

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

예제 입력 1 복사

10

예제 출력 1 복사

2

예제 입력 2 복사

3

예제 출력 2 복사

0

 

 

문제 풀이:

-

0	1	0	2^0
1	1	0	2^0
2	2	0	2^1
3	6	0	2^1*3^1
4	24	0	2^3*3
5	120	1	2^4*3*5
6	720	1	...
7	5040	1	...
8	40320	1	...
9	362880	1	...
10	3628800	2	...
11	39916800	2	...
12	479001600	2	...
13	6227020800	2	...
14	62270202800	2	...
15	87178291200	3	...
16	20922789888000	3	2와 5의 존재

규칙성이 있다.

1~4까지는 0의 개수가 0개

5~9까지는 1개

10~14까지는 2개

이런식으로 1개씩 5의 배수마다 증가합니다.

5의 배수에서 부터는 2와 5의 개수로 인해서 뒷자리에 0이 하나씩 생기게 됩니다.

즉 10팩토리얼의 경우 2의 개수는 많고 5,10이 있기때문에 뒤에서 0이 2개가 발생하는 조건이 생기게됩니다.

그럼 15!의 경우에선 5,10,15 3가지로 3개, 20은 4개 이런식으로 존재하게됩니다.

즉 반복문을 통해 5로 나누면서 값을 적립하는 누적문을 이뤄주면 된다.

 

 

이를 코드로 구현화 하면

		while (num >= 5) {
			count += num / 5;
			num /= 5;
		}

짧은 코드로도 명제가 완성됩니다.

 

 

 

 

 

 

 

 

메인 코드

import java.util.Scanner;
 
public class Main {
 
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
 
		int num = in.nextInt();
		int count = 0;
 
		while (num >= 5) { // 5로 나누면서 누적합을 실행해줘야한다.5이상인 이유는 5이하에서는 0이기때문
			count += num / 5;// 5로 나눠질때까지 넣어준다 5의 개수 도출을 위함
			num /= 5;
		}
		System.out.println(count);
	}
 
}