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

1477번 : 휴게소 세우기

---

문제)

다솜이는 유료 고속도로를 가지고 있다. 다솜이는 현재 고속도로에 휴게소를 N개 가지고 있는데, 휴게소의 위치는 고속도로의 시작으로부터 얼만큼 떨어져 있는지로 주어진다. 다솜이는 지금 휴게소를 M개 더 세우려고 한다.

다솜이는 이미 휴게소가 있는 곳에 휴게소를 또 세울 수 없고, 고속도로의 끝에도 휴게소를 세울 수 없다. 휴게소는 정수 위치에만 세울 수 있다.

다솜이는 이 고속도로를 이용할 때, 모든 휴게소를 방문한다. 다솜이는 휴게소를 M개 더 지어서 휴게소가 없는 구간의 길이의 최댓값을 최소로 하려고 한다. (반드시 M개를 모두 지어야 한다.)

예를 들어, 고속도로의 길이가 1000이고, 현재 휴게소가 {200, 701, 800}에 있고, 휴게소를 1개 더 세우려고 한다고 해보자.

일단, 지금 이 고속도로를 타고 달릴 때, 휴게소가 없는 구간의 최댓값은 200~701구간인 501이다. 하지만, 새로운 휴게소를 451구간에 짓게 되면, 최대가 251이 되어서 최소가 된다.

 

 

 

입력 :

첫째 줄에 현재 휴게소의 개수 N, 더 지으려고 하는 휴게소의 개수 M, 고속도로의 길이 L이 주어진다. 둘째 줄에 현재 휴게소의 위치가 공백을 사이에 두고 주어진다. N = 0인 경우 둘째 줄은 빈 줄이다.

 

 

 

출력 :

첫째 줄에 M개의 휴게소를 짓고 난 후에 휴게소가 없는 구간의 최댓값의 최솟값을 출력한다.

 

 

 

 

 

풀이)

 

// 1477. 휴게소 세우기
#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
 
using namespace std;
 
int n, m, l;
// 휴게소의 배열
vector<int> vec;
 
// 각 휴게소의 거리를 담은 배열
vector<int> diff;
 
bool check(int x)
{
    // x거리로 설치하는 휴게소의 개수
    int cnt = 0;
 
    for (int i = 0; i < diff.size(); i++)
    {
        cnt += diff[i] / x;
 
        // 만약 140구간에서 70의 거리로 설치한다고 하면
        // 휴게소를 1개만 설치해도 되므로
        // 나누어 떨어진다면 cnt--를 해야 한다.
        if (diff[i] % x == 0) cnt--;
    }
 
    // x거리로 자르면 m개 이상 설치 가능
    return cnt > m;
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    cin >> n >> m >> l;
    vec.resize(n, 0);
 
    for (auto& ele : vec) cin >> ele;
    vec.push_back(0);
    vec.push_back(l);
 
    sort(vec.begin(), vec.end());
 
    for (int i = 0; i < n + 1; i++)
    {
        diff.push_back(vec[i + 1] - vec[i]);
    }
 
    // 휴게소의 위치 조건
    int s = 1;
    int e = l - 1;
 
    int ans = 0;
    while (s <= e)
    {
        int mid = (s + e) / 2;
    
        // 최댓값의 최솟값이므로
        // 가능한 것들 중 가장 작은 것을 찾아야 한다.
        if (check(mid))
        {
            s = mid + 1;
        }
        else
        {
            ans = mid;
            e = mid - 1;
        }
    }
 
    cout << ans;
 
    return 0;
}
 

---

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

1477번: 휴게소 세우기