🌞문제

🌞접근법

조건1. 출발지점부터 distance만큼 떨어질 곳이 도착지점 이다.
조건2. 그 사이에 바위들이 놓여있는데, 이것들을 제거 하려고 한다.
조건3. 바위 n개를 지울려고 하는데, 이때 이 바위를 지우는 모든 경우의 수를 구해야한다.
조건4. 이렇게 모든 경우의 수를 구했다면 바위 사이의 최솟값을 구해야 한다.
조건5. distance는 1~10억
조건6. 바위는 1~5만개
조건7. n은 1~바위의 개수

구해야 하는 값 : 조건4에서 구한 최솟값들 중에서의 최댓값

일단 n개를 제외하는 모든 경우의 수를 생각해보자.
이경우를 어떻게 구할 것인가?

처음 생각한 방법은 dfs 였는데, 이렇게 하게되면 너무 오랜 시간이 걸릴 것이다.

그러면 제외하는 경우를 생각하지 말고,
돌 사이의 거리에 대한 최솟값을 크게 하는 방법에 대하여 생각을 해보자.

먼저 임의의 값 하나를 지정하여서 그 값을 최솟값으로 잡는다.

그리고 나서 rocks를 돌면서 rocks의 뒷값에서 앞 값을 빼준다. 그 결과가 임의로 지정한 값보다 작다면
현재 고른 값이 최솟값이 되지 못하기 떄문에 뒤에 돌을 지워준다.

이 과정을 모두 거쳐서 돌을 지운 횟수를 카운팅 해준다.

그 카운팅 한 결과가 n숫자보다 크다면 너무 많은 돌을 지웠다는 것이다.

그 뜻은 더 적게 돌을 지워도 된다는 소리고,
돌을 더 적게 지운다는 것은 최솟값으로 선택한 임의의 값보다 더 큰 값을 설정을 하더라도 괜찮다는 것이 된다.

이에따라 다시 mid 값을 정해주고, 위의 행동을 반복해준다.

🌞풀이

#include <string>
#include <vector>
#include <algorithm>
using namespace std;
int solution(int distance, vector<int> rocks, int n) {
    int answer = 0;
    sort(rocks.begin(),rocks.end());
    
    int start = 0;
    int end = distance;
    while(start <= end){
        int mid = (start + end) / 2;
        int cnt = 0;
        int left = 0;
        
        for(int i=0;i<rocks.size();i++){
            if(rocks[i] - left >= mid) left = rocks[i];
            else cnt++;
        }
        
        if(cnt > n) {
            end = mid - 1;
        }
        else{
            answer = max(answer,mid);
            start = mid + 1;
        }
    }
    
    return answer;
}