분류 : 이진탐색

이진탐색 → 답이되는 수(거리의 최소값 중 최대값)를 이진탐색하는 문제

left : 답이 될 수 있는 가장 작은 값

right : 답이 될 수 있는 가장 큰 값

mid : left와 right의 그 중앙값

경우의 수

• 돌을 다 삭제하고 난 후에 중간값(mid)보다 거리가 작은게 있다면 답이 아님

  ⇒ right = mid -1

• 돌을 다 삭제하고 난 후에 중간값(mid)보다 거리가 작은게 없다면 답임

  이 경우 더 최선의 경우(더 큰값)를 찾기 위해

  ⇒ left = mid +1

알고리즘 순서

1. rocks를 정렬한다.

   sort(rocks.begin(), rocks.end());
   

2. 각각 바위들 사이의 거리를 구하여 dist(vector)에 넣는다.

   rocks.push_back(distance);
       vector<int> dist = { rocks[0] };
       for (int i = 1; i < rocks.size(); i++) {
           dist.push_back(rocks[i] - rocks[i - 1]);
       }
   

3. left와 right를 구한다.

int left = *min_element(dist.begin(), dist.end());
int right = *max_element(dist.begin(), dist.end());

1. mid를 구하고 필요한 변수를 초기화 한다.

while (left <= right) {
        int mid = (left + right) / 2;
        int rest = n; //남은 삭제 개수
        bool flag = false; //삭제 개수를 넘은 경우
        vector<int> tmp; tmp.assign(dist.begin(), dist.end());

1. tmp를 돌면서 mid보다 거리가 짧은 돌을 삭제해 거리를 넓힌다. 만약 삭제 개수를 초과한다면 for문을 빠져나와 right를 줄여준다.

for (int i = 0; i < tmp.size() - 1; i++) {
            if (tmp[i] < mid) {
                if (rest > 0) {
                    rest--;
                    tmp[i + 1] += tmp[i];
                    tmp.erase(tmp.begin() + i);
                    i--;
                }
                else {
                    flag = true;
                    break;
                }
            }
        }
				if (flag) {
            right = mid - 1;
            continue;
        }