[백준] Social Distancing

https://www.acmicpc.net/problem/18877

18877번: Social Distancing

이분탐색을 이용하는 문제입니다.

 

문제부터 간단하게 요약하면, 잔디의 구간들이 M개 있는데, 이 구간에 N마리의 소를 배치해야 합니다. 하지만 소 사이에 병이 퍼지지 않게 하기 위해서 소들을 떨어뜨려 놓으려 합니다. D를 가장 가까운 소 두마리 사이의 거리라고 할 때, D의 가능한 큰 값을 구해야 합니다. 

 

<Solution>

D의 값을 이분탐색 하면 되는 문제입니다. 

 

최소 소의 간격을 1, 최대는 grass중 가장 끝 구간의 마지막 값을 소의 마릿수-1로 나눈 값으로 설정하였습니다.

(사실 그냥 대충 아주 큰 값 이런 형태로 잡아도 가능하기는 할 것입니다. 이분탐색의 시간복잡도는 O(logN)이므로)

 

그리고 잔디를 간격 순으로 sorting 하고, D 값을 이분탐색 하며,is_possible 함수에서 해당하는 간격으로 소를 배치할 수 있는지 없는지를 check하면 됩니다. 

 

주의해야 하는점은 

1. 다음 잔디를 탐색할 때, 이전위치+D > 다음 잔디의 마지막위치 면 skip해야함 2. 이전 위치 +D 값이 다음 잔디의 시작지점 보다 뒤에 있는지 등에 따라 다르게 설정해주어야 함.

2번 조건에 대해서는 다음과 같이 해줍니다. 

        // start index
        cur_index = (cur_index+k <= grass_[i].A) ? grass_[i].A : cur_index+k;

 

실제 구현은 아래와 같습니다.

#include <iostream>
#include <algorithm>
using namespace std;
#define MAXNM ((int)1e5)
int N, M;//소마리수, 잔디구간 개수
 
struct grass{
    long long A, B;
}grass_[MAXNM+10];
 
void InputData(){
    cin >> N >> M;
    for (int i=0 ; i<M ; i++){
        cin >> grass_[i].A >> grass_[i].B;
    }
}
 
bool compare(struct grass a, struct grass b){
    return a.A < b.A;
}
bool is_possible(long long k){
    long long cur_index = grass_[0].A;
    int num_cow = N;
 
    // first grass 
    num_cow -= ((grass_[0].B-grass_[0].A)/k + 1);
    cur_index +=((grass_[0].B-grass_[0].A)/k * k);

 
    for(int i = 1; i<M; i++){
        if(cur_index+k > grass_[i].B) continue;
 
        // start index
        cur_index = (cur_index+k <= grass_[i].A) ? grass_[i].A : cur_index+k;
         
        num_cow-= (grass_[i].B-cur_index)/k + 1;
        cur_index+= (grass_[i].B-cur_index)/k * k;
 
        if(num_cow <= 0) return true;
    }
    // cout << "FALSE" <<endl;
    if(num_cow <= 0) return true;
 
    return false;
 
}
 
long long solution(){
    // sort grass
    sort(grass_, grass_+M, compare);
 
    // binary search
 
    long long s = 1;
    long long e = (grass_[M-1].B) / (N-1);
    long long sol = -1;
    while(e>=s){
        long long mid = (s+e)/2;
        if(is_possible(mid)){
            sol = mid;
            s = mid+1;
        }
        else{
            e = mid-1;
        }
 
    }
 
    return sol;
}
 
 
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    long long ans = -1;
    InputData();// 입력받는 부분
 
    // 여기서부터 작성
    ans = solution();
 
    cout << ans << "\n";// 출력하는 부분
    return 0;
}