[백준/Python] 17266번 어두운 굴다리

풀이

이분 탐색을 통해 가로등의 높이를 찾아주면 됩니다. 가운데의 값(mid)이 굴다리 모든 길을 밝힐 수 있는 가로등의 높이라면 그 값을 result 변수에 저장해둔 뒤, 해당 값보다 더 작으면서 굴다리 모든 길을 밝힐 수 있는 또 다른 가로등의 높이를 찾기 위해 반복해줍니다.

 

그렇게 되면, 이분 탐색이 끝날 때는 result 에는 가장 값이 작으면서도 굴다리 모든 길을 밝힐 수 있는 가로등의 높이가 저장되어 있을 겁니다.

 

'canLight()' 함수는 가로등의 높이가 주어질 때, 해당 가로등의 높이로 굴다리 모든 길을 밝힐 수 있는 지 없는지 True, False 를 리턴해줍니다. 이 때, prev 변수는 이전 가로등이 비춘 최대 위치입니다.

 

import sys

n = int(sys.stdin.readline().rstrip())
m = int(sys.stdin.readline().rstrip())
streetLamp = list(map(int, sys.stdin.readline().rstrip().split()))


def canLight(h):
    prev = 0
    for s in streetLamp:
        if s - h <= prev:
            prev = s + h
        else:
            return False
    
    return prev >= n


start = 1
end = n
result = 1

while start <= end:
    mid = (start + end) // 2
    if canLight(mid):
        end = mid - 1
        result = mid
    else:
        start = mid + 1

print(result)