[ 백준 ] 1477번 - 휴게소 세우기 (C++)

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

1477번: 휴게소 세우기

 

 

[ 문제풀이 ]

 

1. 휴게소의 위치를 1부터 N까지 입력받고, 배열을 오름차순으로 정렬합니다. 이때, 0번 인덱스의 값은 0, N+1번 인덱스의 값은 L로 설정합니다.

 

2. 공유기의 간격이 최소 1에서 최대 999이므로 left = 1, right = 1,000으로 설정하고, 이분 탐색을 진행해 줍니다. 

 

3. mid = (left + right) / 2로 설정하고, 0번 째 인덱스를 기준으로 해당 mid 값보다 더 떨어져 있는 휴게소가 없다면 cnt++를 해주고, 다음 휴게소가 나올 때까지 mid를 더해줍니다. 다음 휴게소가 나오면 기준을 해당 휴게소로 바꿔줍니다. 이를 반복하며 cnt가 M보다 크다면 left = mid + 1이 되고, 그렇지 않다면 right = mid가 됩니다. 

 

4. mid 값 중 가장 작은 값을 출력합니다.

 

[ 소스코드 ]

#include<iostream>
#include<algorithm>
 
using namespace std;
 
int N, M, L;
int arr[152];
 
bool check(int mid)
{
    int base = arr[0];
    int cnt = 0;
 
    for (int i = 0; i <= N; i++) {
        while (1) {
            base += mid;
            if (base >= arr[i + 1]) break;
            cnt++;
        }
 
        if (cnt > M) return false;
        base = arr[i + 1];
    }
 
    return true;
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> N >> M >> L;
 
    for (int i = 1; i <= N; i++) {
        cin >> arr[i];
    }
 
    arr[0] = 0;
    arr[N + 1] = L;
 
    sort(arr, arr + N + 2);
 
    int left = 1;
    int right = 1000;
    int ans = 987654321;
 
    while (left < right) {
        int mid = (left + right) / 2;
 
        if (check(mid)) {
            ans = min(ans, mid);
            right = mid;
        }
        else {
            left = mid + 1;
        }
    }
 
    cout << ans;
}