문제
풀이
이 문제 역시 이분탐색으로 시간초과를 면해야 하는 문제이다. 주어진 testcase에서 가장 높은 것을 right로, 1을 left로 시작하여 mid보다 크냐 작냐로 이분탐색을 해나간다. mid로 나누었을 때 생긴 랜선 갯수가 주어진 testcase보다 크거나 같을 때 더 큰 값을 탐색하기 위해 left = mid + 1로, 그렇지 않은 경우는 right = mid -1로 범위를 좁혀나간다. 계속해서 실행해나가며, max값을 갱신하여 결과를 찾는다.
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
35
#include <iostream>
#include <vector>
using namespace std;
int main(){
int N, count;
scanf("%d %d", &N, &count);
vector<long long> arr(N);
long long arr_max = 0;
for(int i = 0; i<N; i++){
scanf("%lld", &arr[i]);
arr_max = max(arr_max, arr[i]);
}
long long result = 0;
long long left = 1;
long long right = arr_max;
while(left <= right){
long long mid = (right + left)/2;
long long cnt = 0;
for(int i = 0; i<N; i++){
cnt += arr[i]/mid;
}
if(cnt>= count){
left = mid + 1;
result = max(result, mid);
}
else right = mid - 1;
}
printf("%lld\n", result);
}
