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

✏️ 문제 링크

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

1477번: 휴게소 세우기

 

✏️ 문제 설명

 

✏️ 문제 풀이

사실 문제를 보고도 먼 소린지 도저히 모르겠어가지고 이것저것 찾아보다가 접근 방식이 틀렸다는 것을 깨달았습니다.

처음에는 각 휴게소 사이의 거리들의 최댓값을 이분탐색으로 구한 후 그 차이의 중앙값을 벡터에 넣어주고 다시 정렬하고

이런 방식으로 하는 것을 생각했는데 첫 번째 예제가 안 돌아가지더라고요..

그래서 질문 게시판도 찾아보고 했는데 휴게소를 세우는 위치를 아예 다르게 접근을 해야 하더라구요

하나씩 풀이해보겠습니다.

 

먼저, 벡터에 N개의 휴게소를 입력받고 0과 L을 추가로 push한 뒤 정렬을 해줍니다. 

그리고 이분 탐색을 시작합니다. 이분 탐색의 방식은 아래와 같습니다.

1. 각 휴게소간의 길이(len)를 구한다, mid값 설정(start+end)/2

2. cnt = len/mid로 설정, 여기서 cnt는 두 휴게소 간의 지을 수 있는 휴게소의 개수를 뜻합니다.

3. 만약 cnt>0이라면, 즉 휴게소를 지을 수 있다면 두 가지 경우의 수로 나누어 집니다.

    len이 mid의 배수인 경우 => 이러면 끝 지점도 포함되기 때문에 1을 빼준 값을 더해주어야 합니다.

    그게 아니라면 cnt를 그대로 더해줍니다.

4. 2~3번까지 for문을 돌리고 나면 count값에 따라서 경우를 나누어줍니다.

   -먼저 count가 M보다 크다면 안되는 경우이므로 구간을 뒤쪽으로 떙겨줍니다. (start=mid+1)

   뒤쪽으로 떙겨야지 for문에서 mid값이 커져서 count값이 줄어들 수 있습니다.

   -count가 M보다 작거나 같다면 mid값이 크다고 판단할 수 있기 때문에 end=mid-1로 줄여줍니다.

5. 위 과정을 반복하면서 mid의 최솟값을 구해줍니다.

✏️ 문제 코드

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

using namespace std;

int main() {
    cin.tie(0); cout.tie(0); ios::sync_with_stdio(0);
    int N, M, L;
    cin >> N >> M >> L;

    vector<int> v(N);
    for (int i = 0; i < N; i++) cin >> v[i];

    // 거리 차를 구하기 위해 시작 위치와 끝 위치를 추가
    v.push_back(0);
    v.push_back(L);
    sort(v.begin(), v.end()); // 오름차순 정렬

    int start = 1;
    int end = L - 1; // 고속도로 끝에는 못지음
    int mid;
    int ans = 9999;

    // 이분탐색 시작
    while (start <= end) {
        mid = (start + end) / 2;
        int count = 0; // 현재 지은 휴게소 갯수
        // 두 휴게소 사이의 거리 차
        for (int i = 1; i < v.size(); i++) {
            int len = v[i] - v[i - 1];

            int cnt = len / mid; // 두 휴게소 사이에 지을 수 있는 휴게소 개수
            if (cnt > 0) {
                // 딱 맞아떨어진다는 것은 마지막 휴게소와 겹쳤다는 뜻이므로 하나 빼줌
                if (len % mid == 0) count += cnt - 1;
                else count += cnt;
            }
        }
        if (count > M) start = mid + 1; // 개수가 M보다 많으므로 간격 넓혀줌
        else {
            // 개수가 M보다 적으므로 간격 줄여줌
            end = mid - 1;
            // M개의 휴게소 간격이 모두 일정할 순 없음
            // 우리가 구하고자 하는 것은 최소한의 경우 중 가장 긴 것
            ans = min(ans, mid);
        }
    }
    cout << ans;
}

 

 

 

이분껄 참고해서 풀었습니다!

https://howudong.tistory.com/260

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