[백준 / BOJ] 1676번 팩토리얼 0의 개수 (C++, Python)

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

1676번: 팩토리얼 0의 개수

---

문제

---

문제 풀이

나의 수학실력에 다시 한번 감탄하게 된 문제다. 분명 난이도는 실버 5인데 풀리지가 않아서..

 

당연하게도 N이 500까지이므로 N!을 직접 구해 해결하는 방법은 불가능하다. 이 문제의 핵심은 뒤에 0이 나오는 경우는 10이 곱해졌을 때라는 것을 알아차리는데에 있다. 그렇다면 0의 개수는 어떻게 구할까?

10의 0의 갯수는 1개이고, 이는 2 x 5다.

100에서 0의 갯수는 2개이고, 이는 2 x 2 x 5 x 5다.

200에서 0의 갯수는 2개이고, 이는 2 x 2 x 2 x 5 x 5다.

1000에서 0의 갯수는 3개이고, 이는 2 x 2 x 2 x 5 x 5 x 5다.

 

요점은 10이 몇번 곱해졌는지를 알아야 하고, 이는 소인수분해 했을 때 5의 개수와 같다. (2보다 5가 적게 나오기 때문에)

그러므로 N!은 N * (N-1) * (N-2) ...와 같으니 N을 입력받았을 때 1부터 N까지 각각의 수마다 5가 얼마나 나오냐를 체크해주면 된다.

 

+) 파이썬 코드를 찾아보던 중 이 분의 풀이가 신박한 것 같아 첨부해봅니다.

 

 

C++ 코드 전문

	#include <algorithm>
	#include <iostream>
	#include <vector>
	void init() {
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(nullptr);
	std::cout.tie(nullptr);
	}
	int main() {
	init();
	int N, res = 0;
	std::cin >> N;
	for (int i = 1; i <= N; ++i) {
	int cnt = i;
	while (cnt >= 1) {
	if (cnt % 5 == 0) {
	res++;
	cnt /= 5;
	}
	else
	break;
	}
	}
	std::cout << res;
	return 0;
	}

view raw 1676_팩토리얼 0의 개수 (22.06.13 성공, 다시 풀어보기).cpp hosted with ❤ by GitHub

 

Python 코드 전문

	import sys
	input = sys.stdin.readline
	N = int(input())
	res = 0
	for i in range(1, N + 1):
	cnt = i
	while cnt >= 1:
	if cnt % 5 == 0:
	res += 1
	cnt //= 5
	else:
	break
	print(res)

view raw 1676_팩토리얼 0의 개수 (22.06.13 성공, 다시 풀어보기).py hosted with ❤ by GitHub

 

소감

수학은 너무.. 어렵다..