[백준/Baekjoon] 17266 어두운 굴다리 C++ :: Binary Search

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

17266번: 어두운 굴다리

---

1. Logic

값이 참이 되는 구간을 살펴보면 정답 mid를 기준으로 0~left까지는 false, right~n까지는 true이다. 여기서는 참이 되는 값중 최솟값을 구해야 하기 때문에 right를 반환해 주면 된다.

 

---

2. Code

#include <iostream>
#include <vector>

using namespace std;

int n, m;

vector<int> input;

int binarySearch() {
    int start = 0;
    int end = n;
    int mid;
    
    while(start + 1 < end) {
        bool check = false;
        mid = (start + end) / 2;
        if(input[0] > mid) check = true;
        for(int i = 0; i < m-1; i++) {
            if(input[i+1]-input[i] > mid * 2) {
                check = true;
                break;
            }
        }
        if(n-input[m-1] > mid) check = true;
        
        if(check) start = mid;
        else end = mid;
    }
    return end;
}

int main() {
    ios_base::sync_with_stdio(false);cin.tie(0); cout.tie(0);
    cin >> n >> m;
    
    for(int i = 0; i < m; i++) {
        int light;
        cin >> light;
        
        input.push_back(light);
    }
    
    cout << binarySearch();
}

---

3. Feedback

이분탐색 나 이해 했을지도..?

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

728x90