[BOJ] 1676번 : 팩토리얼 0의 개수

1. problem : 

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

 

2. solution 1 :

#include <bits/stdc++.h>
using namespace std;
int n; 

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n; 
	int cnt = 0;
	for (int i = 5; i <= n; i *= 5) {
		cnt += n / i; 
	}
	cout << cnt << '\n';
}

0이 생기기 위해서는 10이 곱해져야 한다. 10은 2 * 5로, 2와 5의 배수를 찾으면 된다. 하지만, 2의 배수보다 5의 배수가 적기 때문에, 5의 배수의 개수를 세면 된다. 이때, 5의 제곱수는 5의 개수가 제곱승만큼 존재하게 된다. 예를 들어, 5^2은 5가 2개 존재한다. 따라서, 5의 배수, 25의 배수 그리고 125의 배수를 차례차례 더해줘야 한다. 이렇게 해야, 누락되는 값이 없다. 

 

3. solution 2 :

// Authored by : jihwan0123
// Co-authored by : -
// http://boj.kr/357ccbb40d504081b55f2d3f98590af4
#include <bits/stdc++.h>
using namespace std;
int main(void) {
  ios::sync_with_stdio(0);
  cin.tie(0);
  int n;
  cin >> n;
  int ans = 0;
  while (n) {
    ans += n / 5;
    n /= 5;
  }
  cout << ans;
}
/*
10을 곱해야 0이 추가되므로 10이 몇번 곱해지는지 세면 된다.
10은 2 x 5 로 소인수 분해가 되는데 2의 배수가 5의 배수보다 많기 때문에 5의 개수만 세면 된다.
*/

source code 출처 : https://github.com/encrypted-def/basic-algo-lecture/blob/master/0x12/solutions/1676.cpp

basic-algo-lecture/0x12/solutions/1676.cpp at master · encrypted-def/basic-algo-lecture