[알고리즘] 백준 파이썬 17266 어두운 굴다리

📍 문제 탐색하기

어두운 굴다리 문제는 길이 N의 굴다리에서, 설치된 M개의 가로등이 굴다리 전체를 밝힐 수 있도록 최소한의 높이 HHH를 계산하는 문제이다.
각 가로등은 높이HH만큼 주위를 밝힐 수 있으며, 모든 가로등의 높이는 동일해야 한다.

---

문제 조건

• 굴다리 길이 N: 1≤N≤100,000
• 가로등 개수 M: 1≤M≤N
• 가로등 위치 x: M개의 가로등 위치가 오름차순으로 주어진다.
• 가로등의 높이 H: x에서 왼쪽으로 H, 오른쪽으로 H 범위를 밝힌다.

---

출력 조건

• 모든 구간(길이 0부터 N)이 밝아지도록 하는 최소 높이 H를 출력한다.

---

입력 범위

• 가로등 위치는 오름차순으로 주어짐.
• 모든 가로등 높이는 동일해야 함.
• 굴다리 길이가 크기 때문에, 선형 탐색 대신 이분 탐색이 필요하다.

---

가능한 시간 복잡도

• 이분 탐색: log⁡N
• 가로등 위치 탐색: M
• 총 시간 복잡도: O(Mlog⁡N)

---

📍 코드 설계하기

1. 이분 탐색 설정
   • 최소 높이(start)는 1, 최대 높이(endendend)는 N
   • 중간값(mid)으로 모든 구간을 밝힐 수 있는지 확인.
2. 모든 구간 커버 여부 확인
   • 각 가로등의 위치를 순회하며, 현재 가로등이 밝힐 수 있는 범위를 계산.
   • 이전 가로등의 범위와 현재 가로등의 범위가 이어지지 않는다면, mid높이로는 불가능.
3. 이분 탐색 진행
   • midmidmid 높이로 가능하다면 end=mid−1
   • midmidmid 높이로 불가능하다면 start=mid+1
4. 최종 출력
   • 최소 높이 H 출력.

---

📍 시도 회차 및 수정 사항

1. 초기 구현
   • start=1, end=N로 설정.
   • 가로등 범위를 순회하며 모든 구간이 커버되는지 확인 후, 조건에 따라 탐색 범위를 줄였다.

---

📍 코드 구현

import sys
input = sys.stdin.readline

N = int(input()) 
M = int(input())  
location = list(map(int, input().split())) 

start = 1  
end = N  

while start <= end:
    mid = (start + end) // 2  
    
    can_illuminate = True
    previous_end = 0  
    
    for pos in location:
        # 현재 가로등이 비출 수 있는 범위가 이전 구간 끝을 덮지 못하면 실패
        if pos - mid > previous_end:
            can_illuminate = False
            break
        # 현재 가로등이 비출 수 있는 범위 끝 갱신
        previous_end = pos + mid
    
    # 마지막 구간까지 비출 수 있는지 확인
    if previous_end < N:
        can_illuminate = False
    
    if can_illuminate:
        end = mid - 1
    else:
        start = mid + 1

print(start)