백준 알고리즘 1676번: 팩토리얼 0의 개수 [C++]

문제 출처: www.acmicpc.net/problem/1676

1676번: 팩토리얼 0의 개수

1. 코드

#include <iostream>

using namespace std;

int main(void)
{
	int n;
	cin >> n;

	int cnt = 0;		//5로 나누는 경우
	
	for (int i = 2; i <= n; i++)
	{
		int temp = i;		//i의 값 임시 저장
		while (temp % 5 == 0)	//5로 나눌 수 없을 때까지 반복
		{
			temp /= 5;
			cnt++;
		}
	}
	cout << cnt;
}

(실행)

2. 풀이

이 문제는 팩토리얼이 전부 진행된 뒤 0의 개수가 몇 개 존재하지는 확인하는 문제인데 그렇다고 팩토리얼을 구한 뒤 0의 개수를 확인하는 것은 사실상 힘들다. 그 이유는 최대 500! 를 구해야 하는데 그렇게 되면 unsigned long long 자료형으로도 오버플로우가 발생하기 때문이다. 그래서 간단하게 10의 약수인 2와 5의 개수를 확인하면 되는데 5가 2에 비해서 적게 나오기 때문에 5의 개수만 세면 답이 나온다.

int n;
cin >> n;

int cnt = 0;		//5로 나누는 경우

팩토리얼을 진행할 수를 입력받고, 5로 나누는 경우를 확인해주는 변수 cnt를 선언해준다.

	for (int i = 2; i <= n; i++)
	{
		int temp = i;		//i의 값 임시 저장
		while (temp % 5 == 0)	//5로 나눌 수 없을 때까지 반복
		{
			temp /= 5;
			cnt++;
		}
	}
	cout << cnt;

반복문을 통해서 2부터 n까지 진행하는데 temp 변수에 i를 저장해준다. 그리고 temp의 값을 5로 나눌 수 없을 때까지 반복하면서 temp의 값을 5로 나누고 cnt의 값을 증가시킨다. 그렇게 i의 값이 n이 될 때까지 반복해준다.

반복문이 끝난 뒤 cnt 값을 출력해주면 문제는 해결된다.

3. 느낀 점

팩토리얼 값이 10에 몇 번 나누어지는지 확인하는 문제라고 처음에 생각을 했지만 알고 보니 5로 몇 번 나누어지는지 확인하는 문제였다.