1676번 팩토리얼 0의 개수

문제링크 : www.acmicpc.net/problem/1676

1676번: 팩토리얼 0의 개수

 

 

<문제 풀이 근거>

N이 500까지 들어올 수 있기 때문에 이를 계산한 값을 구해서 0의 개수를 세려면 변수형 선언이 어렵다.

따라서 뒷자리에 0을 만드는 10을 만들 수 있는 요소를 세는 편이 더 용이하다. 이는 1~N까지의 수들의 약수중 2와 5의 개수를 세는 것을 통해 구할 수 있다.

 

 

 

<알고리즘>

  1) 1~N까지 돌면서 2혹은 5의 배수인 수를 찾는다

  2) 해당 수의 약수에 2의 개수와 5의 개수를 구한다.

  3) 2*5 짝의 개수만큼 0이 생기므로 2의 개수와 5의 개수중 작은 수를 출력

#include <iostream>
#include <string>
using namespace std;

int main() {
	int N = 0;
	cin >> N;
		
	int count_2 = 0;
	int count_5 = 0;

	for (int i = 1; i <= N; i++) {
		int temp = i;
		bool flag = false;
		while (true) {
			if ((temp % 2 == 0) || (temp % 5 == 0)) {
				if (temp % 2 == 0) {
					++count_2;
					temp /= 2;
				}
				else if (temp % 5 == 0) {
					++count_5;
					temp /= 5;
				}
			}
			else break;
		}
	}
	cout << ((count_2 >= count_5) ? count_5 : count_2) << "\n";
	return 0;
}

 

 

+) 참고 : myblog.opendocs.co.kr/archives/1230

[C++ 정리] 자료형의 크기 및 범위 | Opendocs