B1676

개요

백준 문제 1676번을 풀면서 어려웠던 점과 코드를 정리한다.
소요 시간 : 30분
https://www.acmicpc.net/problem/1676

문제

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

코드

#include <iostream>
using namespace std;


void solve()
{
	int num = 0;
	cin >> num;
	int five=0;
	for(int i=5;i<=num;i*=5)
	{
		five += num / i;
	}
	cout << five;
}



int main()
{
	solve();
}

풀이

우선 팩토리얼을 그대로 연산하면 시간초과가 뜬다는 것을 파악했다.
그렇다면 팩토리얼 연산을 하지 않고 어떻게 0의 개수를 파악할까?
정답은 0의 개수 = 10의 개수였다.
따라서 어떤 숫자 N에 대해 2와 5의 갯수를 찾고
그 중 최소값(여기서 최소값은 2와 5가 쌍을 이룰 수 있는 개수)를 찾으면 된다.
하지만 생각해보면 5의 개수는 항상 2의 개수보다 적다 따라서 2는 무시하고 5의 개수만 찾으면 된다.

배울 점, 메모

보통 이런 수학 문제를 만나면 머리가 멍해지는데,
문제를 작게 분해하고 규칙을 찾는 것이 중요한 것 같다.