[BOJ/백준][Gold4] 1477 : 휴게소 세우기 (C++)

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

1477번: 휴게소 세우기

 

 

[난이도] Gold4
[유형] 이분탐색

 

[풀이]
휴게소가 없는 구간의 최댓값을 기준으로 파라메트릭 서치를 해주면 된다.
매 루프마다 나오는 mid값이 휴게소가 없는 구간의 최댓값이며 이 길이를 이용해
휴게소 사이사이에 지을 수 있는 휴게소를 직접 지어보면서 휴게소를 M개 지을 수 있는 것들이
조건에 부업하는 휴게소가 없는 구간의 길이이다. 이 길이가 최댓값이 나올때까지 서치를 진행하면 된다.

 

#include <cstdio>
#include <algorithm>
using namespace std;
int N,M,L,a[102];
int check(int d){
    int ret=0;
    for(int i=1;i<=N+1;i++){
        int diff = a[i]-a[i-1];
        if(diff>d){
            if(diff%d==0) ret+=diff/d-1;
            else ret+=diff/d;
        }
    }
    return ret;
}
int main(){
    scanf("%d%d%d",&N,&M,&L);
    a[0]=0;
    a[N+1]=L;
    for(int i=1;i<=N;i++) scanf("%d",&a[i]);
    sort(a,a+N+2);
    int l=0;
    int r=L;
    while(l+1<r){
        int mid = (l+r)/2;
        int cnt = check(mid);
        if(M<cnt) l=mid;
        else r=mid;
    }
    printf("%d",r);
} 

 

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold4/1477.cpp