2025/02/07 백준 1477 휴게소 세우기

난이도: G4

알고리즘: 이분탐색

 

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

 

1. 문제 탐색

 

제한 시간: 2초, 메모리 제한: 256MB

 

문제에 주어진 휴게소 정보를 이용하여 구간 마다 {휴게소 간 거리, 구간 시작점, 구간 끝점} 이렇게 구조체를 만들고 이것을 우선순위큐에 넣어 거리가 큰 게 먼저오도록 정렬하여 m번마다 pop하고 하나의 구조체를 거리/2하여 두 개로 나누어

2개의 구조체를 다시 push하는 구조로 생각하였다. 이게 문제가 있었다. 같은 지점에는 휴게소를 하나씩만 세울 수 있어서 중복체크를 해야한다는 것인데 이렇게 되면, 하나의 휴게소를 기준으로 옆으로 한 칸씩 휴게소를 세울 수 있는지 체크해야하는 로직이 필요했다. 너무 쓸데없이 복잡해진다는 생각이 들었고, 그냥 휴게소 간 거리에 집중하여, 이분탐색으로 거리를 반씩 줄여가면서 m개의 휴게소를 세울 수 있는지 확인해야겠다는 생각이 들었다.

 

2. 코드 설계하기

맨 앞 구간, 가운데 구간, 맨 끝 구간 이렇게 3개로 나누어 구간별 설치 가능한 휴게소 개수를 구한다.

맨 앞 구간은 1~첫 번째 휴게소, 가운데 구간은 첫 번째 휴게소~마지막 휴게소, 맨 끝 구간은 마지막 휴게소~l-1

이다. 각 구간에서 설치 가능한 휴게소 개수는 (구간의 끝지점 - 구간의 시작지점)/(이분탐색으로 조사중인 거리:k)이다. 

k가 너무 작아지면 추가 설치할 휴게소 개수가 너무 많아질 것이고, k가 너무 커지면 추가 설치할 휴게소 개수가 너무 적어질 것이다.

 

3. 시도회차별 수정 사항

 

1. 우선순위 큐 사용

2. 이분탐색 사용

 

4. 정답코드

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

//휴게소 몇 개 설치하는지 구하는 함수
int cntRest(int dist, int l, vector<int> &rest) {
    int cnt = 0;

    if (rest.size() == 0) { //처음 휴게소 아예 없는 경우
        return (l - 1) / dist;
    }
    cnt += (rest[0] - 1) / dist;
    for (int i = 1; i < rest.size(); i++) {
        cnt += (rest[i] - rest[i - 1] - 1) / dist;
    }
    cnt += (l - rest[rest.size() - 1] - 1) / dist;
    return cnt;
}

//휴게소가 없는 구간의 최댓값 중 최솟값 구하는 함수 - 이분 탐색 
//- 휴게소 개수가 m일 때, 거리보다 거리가 k일 때 휴게소 개수 m이 가능한지 따져보는 게 중요
int lowerSearch(int left, int right, int m, int l, vector<int> &rest) {
    while (left <= right) {
        int mid = (left + right) / 2; //최댓값 설정
        int cnt = cntRest(mid, l, rest); //몇 개 휴게소 설치하는지

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

int main() {
    int n, m, l;

    cin >> n >> m >> l;
    vector<int> rest(n, 0);
    for (int i = 0; i < n; i++) {
        cin >> rest[i];
    }

    //이분탐색을 위한 정렬
    sort(rest.begin(), rest.end());

    cout << lowerSearch(1, l - 1, m, l, rest);
    return 0;
}