백준 17266. 어두운 굴다리

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

17266번: 어두운 굴다리

import sys
input = sys.stdin.readline
n = int(input()) # 굴다리의 길이
m = int(input()) # 가로등의 개수
L = list(map(int,input().split())) # 설치 가능한 가로등의 위치

start, end = 0, n  # 이분 탐색을 위한 시작점과 끝점
ans = n  # 최소 높이의 최대값으로 초기화

while start <= end:
    mid = (start + end) // 2  # 중간값을 이용하여 가로등 높이를 결정
    if L[0] - mid <= 0 and L[-1] + mid >= n: # 굴다리 양 끝을 비추는지 체크
        isCovered = True
    else:
        isCovered = False

    for i in range(1, m):
        if L[i - 1] + mid < L[i] - mid:  # 가로등 사이의 어두운 구간이 있는지 체크
            isCovered = False
            break

    if isCovered:  # 전체 굴다리를 비출 수 있다면, 높이를 줄여본다
        ans = min(ans, mid)
        end = mid - 1
    else:  # 비출 수 없다면, 높이를 높여야 한다
        start = mid + 1

print(ans)