- 문제 설명
- 문제 풀이
N의 수가 2 <= N <= 200,000 이므로 O(n^2)의 시간복잡도로 풀 경우 시간 초과가 발생한다.
때문에 적어도 O(log(n)*n)의 시간복잡도를 유의해야 한다. 그렇기 때문에 이분 탐색을 이용하는 문제라고 유추할 수 있다.
주어진 입력값은 무작위 x좌표로 주어지기 때문에 이분 탐색을 위해 우선 수를 오름차순으로 정렬할 필요가 있다.
<예제 입력 1> 을 예시로 든다면
Index | 0 | 1 | 2 | 3 | 4 |
x | 1 | 2 | 4 | 8 | 9 |
이 상태로 시작을 해야 한다.
공유기는 최소 2개 이상으로 주어지므로 한개는 적어도 첫 번째 인덱스(제일 낮은 값)에 배치할 수 있다.
s를 이론상 최소 거리라고 하고, e를 이론상(N=2) 최대 거리라고 한다면
s = 1
e = arr[N-1] - arr[0]
라고 할 수 있다.
이의 중간값을 mid = (s + e) / 2 라고 하고, 오름 차순을 한 배열을 순차적으로 돌면서 mid값 만큼 떨어진다면 공유기를 설치할 수 있고 그 위치를 기준으로 다시 떨어진 거리를 계산하며 mid값 만큼 떨어졌을 때 공유기를 설치한다고 하자.
참고로 공유기 한개는 첫번째 인덱스에서 설치를 했다는 것을 기준으로 시작한다.
최종적으로 공유기 설치 개수를 세어보고, 가지고 있는 공유기 수 보다 많냐 적냐로 s값과 e값을 mid + 1, mid - 1 로갱신하며 s > e가 될때 까지 최적값을 계산한다.
- 코드
#include <iostream>
#include <algorithm>
using namespace std;
int N, C, s, e, mid, spot, router, ans = 0;
int arr[200000];
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> N >> C;
for (int i = 0; i < N; i++)
cin >> arr[i];
sort(arr, arr + N);
s = 1; // 최소 거리
e = arr[N - 1] - arr[0]; // 최대 거리
while (s <= e)
{
mid = (s + e) / 2;
router = 1; // 공유기 설치 갯수. 1인 이유는 첫번째 위치는 무조건 넣으므로
spot = arr[0]; // 첫번째 위치를 스팟으로 시작
for (int i = 1; i < N; i++)
{
if (arr[i] - spot >= mid)
{
router++; // mid만큼 인접거리가 늘어나면 공유기 설치
spot = arr[i]; // 인접거리 갱신을 위해
}
}
if (router >= C)
{
ans = max(ans, mid);
s = mid + 1;
}
else
{
e = mid - 1;
}
}
cout << ans;
return 0;
}
'Problem Solving > 이분 탐색' 카테고리의 다른 글
[백준] 2805 C++ 나무 자르기 [이분 탐색] (0) | 2023.06.08 |
---|