[백준] 1676 팩토리얼 0의 개수

팩토리얼 0의 개수

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

2 초

128 MB

77545

36650

30670

46.959%

문제

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

입력

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

출력

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

예제 입력 1 복사

10

예제 출력 1 복사

2

예제 입력 2 복사

3

예제 출력 2 복사

0

 

 

문제 말이 이해하기 어려운데, 

N!에서 뒤에서부터 처음 0이 아닌 숫자가 나올 때 까지의 0의 개수를 구해라고 한다.

여기서 "처음 0이 아닌 숫자"라는 말은, 

예를 들어 2100이 있으면, "뒤에서부터"는 1의 자리수부터를 말하는 것이므로 처음 0이 아닌 수는 "1"을 말하는 것이다.

이때까지의 0의 개수를 구하라고 했으므로, 이 예제에서의 답은 "2"이다.

ex) 42340080000 -> 4

 

N 팩토리얼은 1부터 N까지 하나씩 전부 곱하는 연산이다. 또한, 뒷자리에 0이 오려면 10의 배수여야 한다. 10은 2와 5로 소인수분해 되므로, 소인수분해 했을때, 2의 개수와 5의 개수 중 가장 작은 값이 답이다. (2^5 * 5^6 -> 5)

하지만, 우리는 입력을 팩토리얼로 처리하고, 팩토리얼 연산은 1부터 하나하나 곱하기 때문에 소인수 분해시, 5의 개수가 2의 개수보다 더 많은 경우는 없다. 

따라서, 소인수 분해 시 5의 개수를 구하면 된다.

 

주의점으로, 입력 범위가 0~500이므로, 5^1, 5^2, 5^3 이 연산에 있을 수 있으므로, 해당 경우까지 고려해야 한다.

 

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
int main() {
	int num;
	int check_five = 0;
	scanf("%d", &num);
	
	for (int i = 1; i <= num; i++) {
		if (!(i % 5)) {
			check_five++;
			if (!((i / 5) % 5)) {
				check_five++;
				if (!((i / 25) % 5)) {
					check_five++;
				}
			}
		}
			
	}
	printf("%d", check_five);
}