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

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

목차

• 01. 개요
• 02. 접근 방식
• 03. 정답 코드
• 04. 마무리

---

01. 개요

출처

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

 

문제

 

입력

 

출력

 

예시

 

 

---

02. 접근 방식

 

요약

1. 임의의 휴게소 거리를 기준으로 이분 탐색 진행

2. 휴게소 위치에 따른 오름차순 정렬

3. 현재 연속으로 배치되어 있는 두 휴게소 사이의 거리를 임의의 휴게소 거리로 나눠서, 추가해야 할 휴게소 개수 구하기

3-1. 추가해야 할 휴게소 개수가 너무 많다면, 임의의 휴게소 거리를 감소

3-2. 추가해야 할 휴게소 개수가 너무 적다면, 임의의 휴게소 거리를 증가

4. 2번 과정을 반복해 최적의 거리를 구하기

 

과정

 

이 문제는 이분 탐색을 통해서 해결할 수 있습니다.

먼저, 휴게소 위치에 대한 오름차순 정렬을 해야 합니다.

 

현재 고속도로에서 구간에 대한 최대 거리(N)는 1'000입니다.

 

그래서, 임의의 휴게소 거리 시작을 1, 끝을 1'000으로 설정합니다.

 

이에 대한 중간값인 500으로 추가되는 휴게소 개수를 구합니다.

 

추가해야 할 휴게소 개수가 너무 많다면, 끝을 현재 중간값인 500으로 설정합니다.

반대로 추가해야 할 휴게소 개수가 너무 적다면, 시작을 현재 중간값인 500으로 설정합니다.

 

위 과정을 반복하면, 임의의 휴게소 거리는 log(N) 번만 검색하면 됩니다.

 

예제 1번을 통해서 확인해 보겠습니다.

현재 고속도로의 최대 위치는 800입니다.

그래서, 시작을 1과 종료를 800으로 설정하고, 그의 중간인 400을 임의의 휴게소 거리로 지정해서 검사합니다.

 

추가로 시작 위치와 끝 위치도 휴게소 위치로 처리해야 합니다.

두 휴게소 위치 사이의 거리를 임의의 휴게소 거리로 나눠서 추가로 필요한 휴게소 개수를 측정합니다.

거리가 400일 때는 추가로 필요한 휴게소 개수가 0개입니다.

그래서, 개수가 부족하므로, 종류 지점인 800을 중간 지점인 400으로 당겨서 다시 검사합니다.

 

시작을 1로 종료를 400이므로 중간 지점인 200에 대해서 검사를 진행합니다.

거리가 200일 때도 추가 필요 휴게소 개수가 0개입니다.

따라서, 종료 지점을 200으로 설정하고 다시 검사를 진행합니다.

추가 필요 휴게소 개수가 5개로 증가했지만, 목표인 7개에 비해 적습니다.

따라서, 다시 한번 종료 지점을 100으로 설정해서 검사합니다.

 

임의의 거리를 50으로 설정했을 때, 추가 필요 휴게소 개수는 13개입니다.

목표인 7개보다 많기 때문에, 시작을 50으로 설정합니다.

 

위와 같은 과정을 반복해서, 최적의 휴게소 거리를 구해야 합니다.

 

주의점

1. 고속도로의 시작점과 끝점도 하나의 휴게소로 취급해야 합니다.

2. 임의의 거리를 통해서 목표로 하는 추가 휴게소 개수를 구할 때, 해당 목표를 만족하는 최소의 거리를 구해야 합니다. 따라서, 추가 필요 휴게소 개수를 구했음에도 최솟값이 보장되지 않을 수 있습니다. 그러므로, 현재 중간점을 끝점으로 옮겨서 해당 조건을 만족하는 최솟값을 구해야 합니다.

 

---

03. 정답 코드

// 골드 4 - 1477번 : 휴게소 세우기
// 작성자 : free4760(jeonghoe22)

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

using namespace std;

// 현재 조건을 만족하는지 확인
bool isP(const vector<int> &in_dists, const int in_M, const int in_mid)
{
    int add_rest_counts = 0;

    // 현재 간격에서 in_mid(현재 최대 거리라고 가정)를 나눠서 추가로 필요한 휴게소 개수
    for(const int& dist : in_dists)
    {
        // 휴게소를 추가할려면, 1의 공간이 필요
        add_rest_counts += (dist-1) / in_mid;
    }
    
    // 추가로 필요한 휴게소 개수가 더 적을 때, 최소 거리를 증가
    return add_rest_counts <= in_M;
}

int main()
{
    // 입출력 최적화
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    // 현재 휴게소의 개수 N, 추가 휴게소의 개수 M, 고속도로의 개수 L
    int N, M, L;
    cin >> N >> M >> L;

    // 휴게소 위치
    vector<int> rests(N);
    for(int& rest : rests){ cin >> rest; }
    // 처음 위치와 마지막 위치를 휴게소로 생각하고 추가
    rests.push_back(0);
    rests.push_back(L);
    // 오름차순 정렬
    sort(rests.begin(), rests.end());

    // 휴게소 간격 넣기
    vector<int> dists(N+1, 0);
    for(int i = 0; i < rests.size()-1; i++)
    {
        dists[i] = rests[i+1] - rests[i];  
    }
    sort(dists.begin(), dists.end());

    int left = 0;
    int right = dists[N];
    int mid;

    // 거리를 기준으로 측정
    // T T T T F F
    while(left + 1 < right)
    {
        mid = left + ((right - left) >> 1);

        // 거리가 mid라고 가정할 때, 휴게소가 더 필요하므로 최대 거리르 감소
        // mid -> 휴게소간 간격 감소
        if(isP(dists, M, mid))
        {
            right = mid;
        }
        // 휴게소가 더 필요 없으므로 최소 거리를 증가
        // mid -> 휴게소간 간격 증가
        else
        {
            left = mid;
        }
    }

    cout << right << "\n";

    return 0;
}

 

---

04. 마무리

해당 문제를 통해 upper bound와 lower bound에 대해서 이해할 수 있게 되었습니다.

 

---

 

읽어주셔서 감사합니다.

틀린 내용 지적은 언제나 환영입니다!