백준 1477 휴게소 세우기

문제 보기

문제를 푸는 방법을 다음 순서로 고려해봤습니다.

1. Brute Force (완전 탐색)

M개의 휴게소를 모두 배치한 후, 휴게소 사이의 거리 최소값을 구하는 방법입니다.
연산 횟수는 다음과 같습니다.

연산 횟수가 너무 많으므로 사용할 수 없는 방법입니다.

---

2. Greedy

두 개의 휴게소 사이에 ( n )개의 휴게소를 추가한다고 했을 때,
최소 거리를 만들기 위해서는 휴게소를 균등하게 배치해야 합니다.

즉, ( N+1 )개의 공간에 ( M )개를 몇 개씩 넣을지만 결정하면 됩니다.
가능한 모든 경우의 수는 다음과 같습니다.

즉, 중복조합이므로

여전히 연산 횟수가 많으므로 사용할 수 없는 방법입니다.

---

3. DP (동적 계획법)

점화식을 세울 수는 있지만, 최적의 방법을 찾기 어려우며 연산 횟수가 많으므로 적절하지 않다고 판단했습니다.

---

4. 이분 탐색

이분 탐색을 활용하여 휴게소 사이의 최소 거리를 결정하는 방법입니다.

L의 범위가 $100 <= L <= 1000$이므로 연산량이 많지도 않습니다.

1. 조건을 만족하는 최소의 L을 구하는 문제 => 조건 : $start < end$
2. NNNNYYYY의 유형(lower_bound를 구하는 유형) : $mid = (start + end)/2$

/**
 * 1. brute force : 949 C 100 => 너무 크다. 
 * 2. dp : X
 * 3. greedy : 구간 사이에 몇개를 넣을지만 결정 (어차피 n등분 하게 배치해야함)
 * -> 150C100 : 너무 크다
 * 4. 이분 탐색 : 전체 길이가 1000이하이므로 적절하다. 
 */

#include<bits/stdc++.h>

using namespace std;
/**
 *  0 ≤ N ≤ 50
    1 ≤ M ≤ 100
    100 ≤ L ≤ 1,000
 */
int N, M, L;
vector<int> loc, dist;

bool isAble(int x){
    bool flag = false;
    int left = M;
    for(int i = 0;i < dist.size();i++){
        if(dist[i] >= x && dist[i] % x == 0){
            left -= (dist[i]/x - 1);
        }else if(dist[i] >= x && dist[i] % x != 0){
            left -= (dist[i]/x);
        }
    }
    if(left < 0) return false;
    return true;
}

int main(){
    cin >> N >> M >> L;
    loc.push_back(0);
    for(int i = 0; i < N ; i++){
        int input;
        cin >> input;
        loc.push_back(input);
    }
    loc.push_back(L);

    sort(loc.begin(), loc.end());

    for(int i = 1; i <= N + 1;i++){
        dist.push_back(loc[i] - loc[i-1]);
    }

    int start = 1, end = L - 1;

    // 이분탐색
    // NNNNYYYY
    while(start < end){
        int mid = (start + end) / 2;
        if(isAble(mid)){
            end = mid;
        }else{
            start = mid + 1;
        }
    }
    cout << start << endl;

    return 0;
}