BOJ 18877 ) Social Distancing (C++)

18877번: Social Distancing

 잔디의 좌표가 크기때문에 이진탐색을 이용해서 해결했다. 잔디구간이 오름차순으로 들어오지않기 때문에 정렬이 필요하다. 

 high는 가장 마지막 잔디구간의 좌표까지가 모두 잔디구간이라고 가정했을 때 N마리의 소를 세우는 경우로 잡았다. 그냥 마지막 좌표로 잡아도 통과는 하지만 탐색 시간을 최대한 줄이기 위해 다음과 같이 설정했다. 

 isPossible 함수를 통해서 해당 간격으로 소들이 모두 잔디구간에 서 있을 수 있는지를 검사한다. 

 첫번째 소는 무조건 v[0].x(잔디구간의 제일 앞)에 세우기 때문에 cnt를 1로, 바로 앞 소의 위치인 cow를 v[0].x로 하여 시작한다. 잔디구간이 남아있지 않거나 소를 모두 올릴 때 까지 while문을 반복한다.

 앞 소의 위치 + n(간격)가 현재 잔디구간의 끝 좌표(v[i].y)보다 작은 경우 소를 잔디구간에 세운다. 단 cow+n이 v[i].x보다 작은 경우 잔디구간에 올라오지 못했으므로 v[i].x에 소를 세운다. (이 경우 앞 소와의 간격은 cow+n보다 커진다.) cow+n이 잔디구간 위인 경우 해당 자리에 소를 세워준다.(앞 소와의 간격은 n) 

 cow+n이 v[i].y보다 큰 경우 현재 보고 있는 잔디구간에 소를 세울 수 없으므로 다음 잔디구간을 검토한다. 

#include <iostream>
#include <vector>
#include <algorithm>
#define ll long long
#define pll pair<long long, long long>
#define x first
#define y second
using namespace std;

int N, M;
ll a, b;
vector<pll> v;
// 무조건 잔디구간 첫 시작점에 소를 한마리 세움

bool isPossible(ll n){
    int i=0;      // i번째 잔디구간
    ll cow=v[0].x; // 바로 앞 소의 위치
    int cnt=1;   // 서있는 소 마리수
    while(i<M&&cnt<=N){
        if(cow+n<=v[i].y){   // 소가 잔디구간에 위치해있는지 확인
            // 소 위치 변경
            cnt+=1;
            if(cow+n>=v[i].x) cow = cow+n;    // x+n이 잔디구간 위라면 그대로 입력   
            else cow = v[i].x;            // 잔디구간에 도달하지 못했으면 잔디구간의 첫번째 좌표
        } else { 
            i++;    // 다음 잔디구간으로 이동
        }
    }
    if(cnt >= N) {  // N마리가 다 서있음
        return true;
    } else {
        return false;
    }
}


int main(){
    cin.tie(NULL);
    ios_base::sync_with_stdio(false);

    cin>>N>>M;
    for(int i=0;i<M;i++){
        cin>>a>>b;
        v.push_back({a,b});
    }

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

    ll low, mid, high, ans =0;
    low = 0; high = v[M-1].y/(N-1);   
    // high를 구간이 모두 잔디구간일 때 소들이 서있을 수 있는 최대 거리로 가정 
    while(low <= high){
        mid = (low + high)/2;
        if(isPossible(mid)){
            ans = max(mid, ans);    // 둘중 큰 거리로 답을 update
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    cout<<ans;
    return 0;
}