문제
가장 끝의 0의 개수가 M개인 N! 중에서 가장 작은 N을 찾는 프로그램을 작성하시오.
입력
첫째 줄에 M (1 ≤ M ≤ 100,000,000)이 주어진다.
출력
가장 끝의 0의 개수가 M개인 N! 중에서 가장 작은 N을 출력한다. 그러한 N이 없는 경우에는 -1을 출력한다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
|
#include <iostream>
using namespace std;
int binary_search(int m) {
int l = 1, r = 1000000000, mid, cnt, ans;
bool find = false;
while (l <= r) {
cnt = 0;
mid = (l + r) / 2;
for (int i = 5; i <= mid; i *= 5)
cnt += mid / i;
if (m <= cnt) {
if (m == cnt) {
find = true;
ans = mid;
}
r = mid - 1;
} else {
l = mid + 1;
}
}
if (!find)
return -1;
else
return ans;
}
int main() {
int m;
cin >> m;
cout << binary_search(m) << '\n';
return 0;
}
|
cs |
일단 m이 최대 1억이기 때문에 1! 부터 계산하는 방법으로는 시간초과가 날 거 같아서 이분탐색을 사용했다.
n!에서 뒤에 붙는 0의 개수는 n!에 포함된 2와 5의 개수 중에서 작은 값인데 직관적으로 이해하면 항상 5가 적을 것이다.
11~12줄은 그 점을 이용해서 mid!에 포함된 0의 개수를 구하는 과정이다.
그런데 뒤에 m개의 0이 붙는 n!이 없을 수도 있기 때문에 find라는 별도의 bool 변수를 만들어서 처리했다.
'백준 온라인 저지 (BOJ) 문제풀이' 카테고리의 다른 글
| 백준 온라인 저지 1790 수 이어 쓰기 2 (0) | 2020.12.31 |
|---|---|
| 백준 온라인 저지 14492 부울행렬의 부울곱 (0) | 2020.12.30 |
| 백준 온라인 저지 16508 전공책 (1) | 2020.12.24 |
| 백준 4920 테트리스 게임 (0) | 2020.12.14 |
| 백준 온라인 저지 1038 감소하는 수 (0) | 2020.12.09 |
