[Algorithm] Baekjoon 1477번 : 휴게소 세우기

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

 

 

#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <algorithm>
#include <math.h>
#include <queue>
#include <functional>
#include <sstream>
#include <memory.h>
#include <deque>
#include <set>
#include <unordered_map>
#include <stack>
#include <numeric>
#include <climits>
#include <bitset>
#include <cmath>
 
using namespace std;
 
int n, m, l;
vector<int> highways;
 
 
bool check(int mid)
{
    int count = 0;
 
    for (int i = 1; i < highways.size(); ++i)
    {
        int distance = highways[i] - highways[i - 1];
        
        if (distance > mid)
        {
            count += (distance-1) / mid;
        }
    }
 
    return count <= m;
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    cin >> n >> m >> l;
    
    highways.resize(n + 2);
    highways[0] = 0;
    highways[n + 1] = l;
 
    for (int i = 1; i <= n; ++i)
    {
        cin >> highways[i];
    }
 
    sort(highways.begin(), highways.end());
 
    int left = 1;
    int right = l;
    int result = 0;
 
    while (left <= right)
    {
        int mid = (left + right) / 2;
 
        if (check(mid))
        {
            result = mid;
            right = mid - 1;
        }
        else
        {
            left = mid + 1;
        }
    }
 
    cout << result;
}
 
 
 

두세달만에 알고리즘문제를 푸는 것 같다.

 

위 문제는 각 노드사이에 M개만큼의 추가노드를 추가설치할건데, M개를 전부 사용했을 때 각 노드사이의 거리값의 최대값을 최소값으로 만들어어 한다.

 

즉, M개만큼 임의로 막 설치했을 때 각 노드사이의 거리가 100,300,500,14, 이럴 경우, 출력되는 값은 최대값인 500이 된다.

이 최대값들중에 최소값을 구해야하기 때문에 M개만큼의 노드를 '적절하게' 배치 해야 최소값을 구할 수 있을 것이다.

 

단순히 완전탐색으로 노드를 전부 배치하는 경우를 따지면, 경우의 수가 너무많다.

처음 5개의 노드 1,2,3,4,5가 주어진다고 생각해보자.

참고로 처음 주어지는 노드 외에 시작점과 끝점도 노드로 포함시켜야 한다.

문제만 읽었을 때 살짝 헷갈릴 수 있는데, 휴게소사이만 고려하는게 아니다.

그러니 시작점 0과 끝점 L(인풋값)을 벡터에 넣어준다.

 

대충 시작점, 끝점까지 포함해서 노드 1,2,3,4,5가 있다고 생각해보자.

M값은 최대값인 100이라 가정.

첫 경우의 수를 생각해보자.

 

1~2사이에 1개 배치, 2~3사이에 1개 배치, 3~4사이에 1개 배치, 4~5사이에 97개 배치.

대충 감이 온다. 경우의 수가 무지막지하게 많다.

1 1 1 97 , 1 1 2 96, 1 1 3 97 ............ 아 물론 0개를 배치해도 된다.

그럼 다시 0 0 0 100, 0 0 1 99 .... 

 

즉 최대 100개의 과자를, 51(구간의 최대개수)명의 사람한테 '순서있게' 나눠주는 경우의 수가 된다.

그러면 51^100 이되는데... 어마어마하다.

( 혹시 아니라면 댓글 달아주시길 바랍니다)

 

이렇게 경우의 수가 많으면 으레 생각하는 것 중 하나가 이분탐색이다.
적절한 값을 찾기위해 범위를 반씩 줄여가며 탐색하기때문이다.
그럼 이 적절한값, 보통 변수명으로 mid로 작성하는 이 값을 뭘로 해야할까?

사실 이부분은, 이분탐색문제를 많이 풀어봤다면 관성적으로? 알 수 있다.
문제에서 요구하는 답을 mid값으로 먼저 책정해보고 그에 따라 check함수를 한번 생각해본다.
최대값들 중에서 최소값이니, 이 값이 유효한지 검사해서 유효하다면 숫자를 작은쪽으로 범위를 좁혀나가고, 유효하지 않으면 숫자가 큰쪽으로 범위를 좁히면 된다.

그러면 우리가 이제 해야할 것은 특정거리값이 주어졌을 때, m개의 고속도로를 전부 설치했을 경우 각 구간들중의 최대값이 이 특정거리값을 넘냐 안넘냐를 체크하는 것만 구현하면 된다.
먼저 그러기위해 벡터에 n개의 휴게소 위치, 시작점, 끝점 l을 집어 넣고 오름차순정렬을 한번 돌려준다.
그리고 우리는 기준거리값(mid)를 정해놨기 때문에, 이것을 기준으로 각 휴게소 사이마다 최소의 개수로 추가휴게소를 설치한다. m개만큼 설치하는게 아니라, 되는대로 설치 후에 설치개수가 m개를 초과하는지 검사한다.

최소의 개수로 추가휴게소를 설치하기위해선 두 휴게소사이의 거리값을 현재 기준이 되어있는 mid값으로 나누면 된다.

예를들어 현재 mid값이 200이라 가정하자. 그럼 우리는 추가휴게소를 설치했을 때 각 휴게소사이의 거리값이 200을 초과해선 안되며, 최소의 설치개수로 200을 초과안하게 해야한다.
이때 그냥 거리값을 mid값으로 나눠주면 된다.

이 때 거리값-1 을 mid로 나눠줘야 한다. 이건 추가설치로 인한 간격에 대한 보정?같은 느낌인데 그냥 예시로 보는게 제일 이해가 빠르다.

 

0 ~ 400 사이에 mid값 200인상태로 추가휴게소를 설치한다고 가정해보자.

그냥 400을 200으로 나눠버리면 2가 나오니까 휴게소를 두개를 더 설치해야한다는 결과가 나온다.

근데 실제로는 200지점에 한개만 설치해도 mid값 200을 초과하지 않는다.

 

이부분에 대해서는 수학적으로 더 깊은 설명을 하지못해 유감이다.

 

어쨌든 이렇게 끝점까지의 각 구간에 설치를 전부 해줬을 때, 설치한 휴게소의 개수가 m개 이하일 경우, mid값은 유효하다고 판정하고 left와 right값을 더 작은 값의 범위로 이동시켜준다.

 

m개를 전부 설치해야하는데, m개이하이면 유효하다 판단해도되나? 라고 의문을 가질 수 있는데, 어차피 m개만큼 설치가 안됐는데도 mid값이 유효하다면 나머지 남는거는 어떻게 설치하든 별 의미가 없기 때문이다.

이미 최대값 mid를 특정값으로 정해놨기 때문에, 남는거를 어떻게 설치하든 mid값보다 줄면 줄었지 늘어날일은 없기 때문이다.