[BOJ 2110] 공유기 설치

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

공유기를 c 개 이상 설치하는데 그 간격이 가장 크게 배치하는 방법이다.

이 문제의 경우 핵심은 "답을 x라고 가정할 때 그 답이 가능한가?" 라는 질문에 답을하는것이다.

#include<iostream>
#include<string>
#include<stdio.h>
#include<algorithm>
#include<utility>
#include<vector>
#include<cstring>
#include<queue>
#include<cmath>
#include<math.h>
 
using namespace std;
 
int n,c;
int main(){
    scanf("%d%d" , &n,&c);
    vector<int > v(n);
    for(int i=0;i<n;i++){
        scanf("%d" , &v[i]);
    }
    sort(v.begin(),v.end());
    
    int left = 1;
    int right = 1000000000;
    int ans=1;
    
    while(left<=right){
        int mid = (left+right)/2;
        int cnt = 1;
        int pos = 0;
        for(int i=0;i<n;i++){
            if(v[i]-v[pos]>=mid){
                pos = i;
                cnt++;
            }
        }
        if(cnt>=c){
            if (ans < mid) {
                ans = mid;
            }
            left = mid+1;
        }else{
            right = mid-1;
        }
    }
    printf("%d\n" ,ans);
}

mid가 답이 될수 있는 값이라고 가정을 한다. 그리고 이분탐색을 계속 하는것인데 그 때 답인 ans보다 mid가 클 경우 mid가 새로운 ans 가 된다.