(C++) - 백준(BOJ) 17266번 : 어두운 굴다리

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

17266번: 어두운 굴다리

이분탐색 문제였습니다

 

📕 풀이방법

📔 입력 및 초기화

 1. n, m, 가로등의 위치를 저장할 일차원 배열 lamp를 선언합니다. 2. n, m을 입력 받고 m개의 lamp 위치를 입력받습니다.

 

 

📔 풀이과정

가로등의 적절한 위치를 mid로 두어 이분탐색을 시행합니다. 가로등이 제대로 n만큼의 굴다리 길이를 비추는 지 확인하기 위해 구역을 3군데로 나눕니다.

 1. 0번 위치 ~ lamp[0] : 길이는 lamp[0]입니다. 이 만큼 비춰야 하지만 mid가 그보다 작다면 유효하지 않으므로 flag = 1로 세워줍니다.

 2. lamp[1] ~ lamp[m-1] : 길이는 lamp[i+1] - lamp[i]입니다. mid * 2가 이보다 작다면 유효하지 않습니다. flag = 1로 만듭니다.

 3. lamp[m-1] ~ n : 길이는 n - lamp[m-1]입니다. mid가 이보다 작다면 유효하지 않습니다. flag = 1로 만듭니다.

 4. !flag라면 유효한 길이므로 가로등의 높이를 더 줄여볼 수 있습니다. r = mid - 1로 만듭니다. 반대의 경우 가로등의 높이를 늘려줘야 하므로 l = mid + 1이 됩니다.

 

📔 정답출력

함수 binarySearch를 수행한 반환값을 출력합니다.

---

📕 Code

#include <bits/stdc++.h>
using namespace std;
int n, m, lamp[100001];

int binarySearch(){
    int l = 0;
    int r = 100000;
    while(l <= r){
        int mid = (l + r) / 2;
        int flag = 0;
        if(lamp[0] > mid) flag = 1;
        for(int i = 0; i < m - 1; i++){
            if(lamp[i+1] - lamp[i] > mid * 2) { flag = 1; break; }
        }
        if(n - lamp[m-1] > mid) flag = 1;
        
        if(!flag) r = mid - 1;
        else l = mid + 1;
    }
    return l;
}
int main(){
    cin >> n >> m;
    for(int i = 0; i < m; i++) cin >> lamp[i];
    cout << binarySearch();
}