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

1. 문제이해

https://www.acmicpc.net/problem/1676

1676번: 팩토리얼 0의 개수

 

0과 500사이의 수 N을 입력받아, N!의 뒤에서부터 처음으로 0이 아닌 다른 수가 나올때까지

0의 개수를 출력하는 알고리즘을 구현하는 것이 목표이다.

 

 

 

2. 문제풀이

 

N!의 뒤에서부터 처음으로 0이 아닌 다른 수가 나올때까지 0의 개수를 출력하는 문제이다.

예를 들어, 10!은 3628800이므로, 0의 개수가 2개, 3!은 6이므로, 0의 개수가 0개가 된다.

같은 방식으로, 500!은 0의 개수가 124개가 된다.

 

문제에서 구하고자하는 바는 무엇일까?

바로 10(2 x 5)의 개수이다.

예를 들어, 10! 같은 경우에는 , 10 (2 x 5), 9, 8, 7, 6, 5, 4, 3, 2, 1 을 곱한것으로,

2 x 5의 개수가 2개이므로 0의 개수가 2개가 된다.

또 다른 예로, 3600같은 경우 어떤 수의 팩토리얼은 아니지만,

36 x  (2 x 5) x (2 x 5) 이므로 0의 개수가 2개가 된다.

 

문제에서 원하는 0의 개수를 출력하기 위해서는 2 x 5가 몇 개인지를 출력하면 되는데,

여기서 주목해야할 점은 '5'의 개수이다.

2의 배수는 4, 6, 8 등, 5의 배수보다 확연히 많기 때문에,

5의 배수의 개수를 세면, 그것이 자동적으로 10의 배수의 개수가 된다.

5의 제곱, 5의 세제곱의 배수 또한 마찬가지이다.

5의 제곱인 25의 배수는 5가 두개이므로, 10의 배수가 한번에 두개씩 나타나는 것과 같고,

세제곱인 125의 배수는 5가 세개이므로, 10의 배수가 한번에 세번씩 나타나는 것과 같다.

 

예를 들어, 500이라는 수는 5의 배수가 100개, 25의 배수가 20개, 125의 배수가 4개 이므로, 

500!의 뒤에서부터 처음으로 0이 아닌 다른 수가 나올때까지 0의 개수는 100+20+4=124가 된다.

(125, 25의 배수는 각각 5의 배수에 포함되지만, 5의 배수를 셀 때 한 번씩만 카운트하게 된다.

하지만, 사실 25는 2번, 125는 3번 세야하므로, 25, 125의 배수의 개수를 그대로 구하여 더해주어야한다.

위와 같이 500이라는 수에서 5의 배수는 100개 나왔을 때, 25, 125의 배수는 각각 한번, 두번 더 세어주어야 한다.

여기서 25의 배수를 한번 더 더해주면, 125의 배수만 한번 더 카운트 해주어야 하므로,

125의 배수까지 카운트 해주면 모두 알맞게 더한 것이 된다.)

 

즉, 5의 배수의 개수 + 25의 배수의 개수 + 125의 배수의 개수가 주어진 수 N!의 0의 개수가 된다.

(N은 0~500사이의 수 이므로, 5의 네제곱인 625부터는 포함하지 않았다.)

 

 

 

3. 소스코드

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int main() {
	int N;
	int mul5 = 0;	// 5의 배수
	int mul25 = 0;	// 25의 배수
	int mul125 = 0;	// 125의 배수

	scanf("%d", &N);

	mul5 = N / 5;
	mul25 = N / 25;
	mul125 = N / 125;

	printf("%d", mul5 + mul25 + mul125);

	return 0;
}

코드로 구현해보니 생각보다 간단한 문제였다.

(팩토리얼 관련 문제지만, 굳이 팩토리얼을 구할 필요가 없었다.)

N을 입력받고, N까지의 5의배수, 25의 배수, 125의 배수를 세어 모두 더해주어 결괏값을 구했다.

 

 

---

오늘 문제는 제대로 된 풀이방법을 생각하기까지의 시간이 조금 걸렸던 문제였다.

그냥 일반적으로 팩토리얼을 하고 수를 하나하나 배열에 넣어 0의 개수를 셀까? 라는 생각을 했다가,

백준에서는 그런식으로 하면 어김없이 시간초과가 발생했었던게 생각이나서..ㅎㅎ😂

막상 구현해보니 어렵지 않은 문제였던것 같다.

휴가 다녀오고서 첫번째 푸는 문제인데, 내일부터는 다시 열심히 달려야지! 😤