[백준/Baekjoon] 1477 휴게소 세우기 C++ :: Binary Search

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

1477번: 휴게소 세우기

---

1. Logic

처음에 이 문제를 보고  0~L까지 거리를 구한 값을 우선순위 큐에 넣은 다음 큰 숫자부터 2로 나눠서 m만큼 반복하면 쉽게 풀릴 것 같다고 생각했다. 하지만 여기에는 반례가 있었다. 만약 테스트 케이스가 

0 2 100

다음과 같이 주어졌을때를 가정해 보면 먼저 답은 33이 나와야한다.

우선순위 큐에는 0~100까지 100이 들어가있을 것이다. 우선순위 큐로 항상 2로 나눈다면 먼저 0~100을 2로 나눈 50이 들어가기 때문에 0~50, 51~100 이후 0~50을 2로 나눈 0~25, 25~50, 51~100 그래서 오답인 50이 답으로 나오게 되지만 답은 그냥 100중에서 2개를 3등분한 33이 정답이다. 우선순위 큐를 통해 풀수 있는 방법이 있지만 여기서 의도한 대로 이분탐색으로 풀어보았다.

 

로직은 각 구간별 거리를 저장한 후 휴게소를 m개만큼 다 짓는게 최솟값을 구하는 방법이므로 이분탐색을 통해 휴게소를 놓을 수 있는 구간의 거리를 구하여 m개와 같아질 때의 mid값을 구해주면 된다.

 

 

 

---

2. Code

#include<bits/stdc++.h>

using namespace std;

int n, m, l;
vector<int> input;
vector<int> sum;

bool check(int mid) {
    int cnt = 0;
    for(int i = 0; i < n + 1; i++) {
        if(sum[i] % mid == 0) {
            cnt += (sum[i] / mid) - 1;
        }
        else {
            cnt += sum[i] / mid;
        }
    }

    if(cnt <= m) return true;
    else return false;
}

void binarySearch() {
    int start = 0;
    int end = l;

    while(start+1 < end) {
        int mid = (start + end) / 2;

        if(check(mid)) end = mid;
        else start = mid;
    }

    cout << end;
}

int main() {
    cin >> n >> m >> l;

    for(int i = 0; i < n; i++) {
        int a;
        cin >> a;
        input.push_back(a);
    }

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

    int prev = 0;
    for(int i = 0; i < n; i++) {
        sum.push_back(input[i]-prev);
        prev = input[i];
    }
    sum.push_back(l - prev);


    binarySearch();
}

 

 

---

 

3. Feedback

등식(=)이 있는 곳을 기준으로 end=mid이면 최소

등식(=)이 있는 곳을 기준으로 start=mid이면 최대

알고리즘 Solve 후 제가 생각한 Logic을 기록하는 개인 공부 블로그입니다.
내용 중 최적화가 가능한 부분등은 언제든지 댓글로 틀린 부분 및 피드백 주시면 공부 및 반영하겠습니다🧐

728x90