[BOJ/C++] 1477: 휴게소 세우기

🏅 Gold 4

✏️ 1차 솔루션

⭐️ 이분 탐색 풀이
⭐️ 휴게소 간 최적의 거리를 탐색

1. left = 1, right = 고속도로 끝 - 1
   ➡️ 고속도로 시작과 끝에는 휴게소를 세울 수 없기 때문에 이렇게 설정
2. 휴게소 위치 오름차순 정렬
3. 모든 휴게소 간 간격을 mid 간격으로 나누면 휴게소를 추가로 몇 개 세울 수 있는지 계산
   ❗️ 첫 휴게소는 고속도로 시작 위치와의 간격을 계산하고 마지막 휴게소는 고속도로 끝 위치와의 간격 계산해야 함
   ❗️ 기존 휴게소에는 세울 수 없기 때문에 휴게소 간격이 mid 에 나누어 떨어지면 1을 빼줘서 기존 휴게소에 세울 수 없도록 조정 필요
4. 추가로 세운 휴게소 개수가 m 보다 크거나 같으면 휴게소 간 간격을 넓혀서 휴게소 개수를 줄임
   ❗️ 휴게소 간격을 ans 에 최소값 갱신
5. 추가로 세운 휴게소 개수가 m 보다 작으면 휴게소 간 간격을 좁혀서 휴게소 개수를 늘림

🚨 1차 trouble

자꾸 오차가 발생하면서 일부 테케가 안 맞는데 left, right 범위 설정에 문제가 있는 것 같음

✏️ 최종 솔루션

⭐️ 이분 탐색 풀이

• 각 구간에 세울 수 있는 휴게소 개수를 count 할 때, 휴게소를 1개 이상 세울 수 있는 경우에 한해서만 기존 휴게소에 세울 수 있는 경우를 배제해주기
  ❗️ 그렇지 않으면 마이너스 발생
• n 이 0인 경우 예외처리를 따로 해줄 필요 없음
• 휴게소를 m 개 세울 수 있는 경우 중에 최소값을 구해야하기 때문에 m 보다 작거나 같은 경우에 ans 를 갱신하도록 해야함 그렇지 않으면 m 개를 넘어가는 상황에서 m 개를 충족하지 않는데 간격은 최소값을 갖기 때문에 m 개를 충족하는 값을 찾더라도 정답을 산출할 수 없음

📌 self feedback

접근한 방법은 맞았지만 left, right 범위 설정이 부족했고 정답을 갱신하는 시점을 잘못 설정

✏️ 최종 code

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int n,m,l;
    cin >> n >> m >> l;
    
    vector<int> v(n+2);
    v.push_back(0);
    for(int i=0;i<n;i++) {
        cin >> v[i];
    }
    v.push_back(l);
    
    sort(v.begin(),v.end());
    
    
    int left=1,right=l-1,ans=1000;
    while(left<=right) {
        int mid=(left+right)/2;
        
        int cnt=0;
        
        for(int i=1;i<v.size();i++) {
            cnt+=((v[i]-v[i-1])/mid);
            if(cnt>0) {
                if((v[i]-v[i-1])%mid==0) cnt-=1;
            }
            
        }

        if(cnt>m) {
            left=mid+1;
        }
        else {
            ans=min(ans,mid);
            right=mid-1;
        }

    }
    
    cout << ans << endl;
}