[Miracle Baekjoon] 1일차 - 1676번 팩토리얼 0의 개수 - C++

시작하며

 
 안녕하세요. 여러분들은 혹시 미라클 방송이라는 것을 들어보셨나요? 미라클 방송이란 개인방송인이 연속으로 며칠까지 방송하는지를 기록하며 매일 방송하는 것을 말합니다. 저도 유튜버 침착맨의 미라클 방송을 통해서 알게 되었는데요. 방송인들의 미라클 방송을 보며 시청자들도 함께 미라클 OO ex) 미라클 팬아트, 미라클 운동, etc.. 을 한다고 합니다.
 
 그래서 저도 이번에 한번 해보려고 합니다. 제가 선택한 종목은 제목에서 보셨다시피 미라클 백준입니다. 많은 분들이 이미 굳이 생색내지 않으면서 매일 문제를 풀고 계실 텐데요. 저는 굳이 생색내며 한번 도전해 보겠습니다. (사실 어제도 문제 풀어서 2일 차지만 상남자답게 마음먹은 날부터 1일 차로 하기로 함) 그럼 과연 제가 며칠차까지 성공할 수 있을지 함께 지켜봐 주시기 바랍니다!
 
 일단 계획상으로는(?) 매일매일 올릴 것이기 때문에 매일 공들여 쓰긴 어려울 것 같습니다. 그래서 앞으로는 형식을 조금 간소화하려고 합니다. 그래서 보시기에 전보다 조금 불편할 수 있습니다.

---

팩토리얼 0의 개수
 

made by yongjun

 
문제

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

---

입력

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

---

출력

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

---

예제 입력 1 

10

예제 출력 1 

2

 

예제 입력 2 

3

예제 출력 2 

0

---

 

문제풀이

 
 이번문제는 보자마자 overflow에 주목했습니다. 500! 은 굉장히 엄청나게 큰 수이기 때문에 메모리공간에 담으려면 너무 큰 비용이 들거나 overflow가 날 것입니다. 문제의 목적은 끝의 0의 개수만 구하면 되는 것이기 때문에 수 전체를 보지 않아도 풀 수 있습니다. N! 은 다음과 같이 나타낼 수 있습니다.  

N! = Q × 2^x × 5^y

 
 어떤 수 Q는 신경 쓰지 않아도 되고, 2와 5의 지수인 x, y 중 작은 수의 개수만큼 10이 곱해지기 때문에 이것이 곧 끝의 0의 개수라고 할 수 있습니다. 그렇다면 [ N! = N × (N - 1) × (N - 2) × · · · × 1 ]에서 모든 항을 나누어 떨어지지 않을 때까지 2와 5로 나누며 카운트하면 되겠습니다. 한 번에 10으로 나누지 않는 이유는 각 각 다른 항에서 곱해져 있는 2와 5가 만나서 10이 될 수 도 있기 때문입니다.
 

#include <iostream>

using namespace std;

int main(void) {
	int N;    /주어진 수 N
	cin >> N;
    
	int cnt2 = 0, cnt5 = 0;    //2카운터와 5카운터

	for (; N > 0; N--)    //N이 1이될때까지 1씩 빼며 반복
	{
		int copyN = N;
        
		while (copyN % 2 == 0)    //2로 나누어 떨어지지 않을 때까지 반복
		{
			copyN /= 2;
			cnt2++;
		}
		
		while (copyN % 5 == 0)    //5로 나누어 떨어지지 않을 때까지 반복
		{
			copyN /= 5;
			cnt5++;
		}
	}
	cout << ((cnt2 > cnt5) ? cnt5 : cnt2);    //2카운터와 5카운터중 작은 수 출력

	return 0;
}

 
 

마치며

 
 이번 문제는 조금만 생각한다면 풀이도 쉽고 구현도 쉬운 문제라고 생각합니다. 감사합니다.